#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
const int maxn = 2e4 + 5;
const int N = 32768;

int X[8], Y[8];
ull a[N], b[N];

struct info
{
	ull x; int is;
	info(ull X = 0, int I = 0) { x = X; is = I; }
	info operator + (const info &b)const
	{
		if (is == 1) return b;
		if (b.is == 1) return *this;
        if (is == 2 || b.is == 2) return info(0, 2);
		// cout << "A " << x << " " << b.x << "\n"; cout.flush();
		// ull t; cin >> t; return info(t, 0);
        return info(x + b.x, 0);
	}
	
	bool operator < (const info &b)const
	{
		if (is == 1 || b.is == 2) return true; if (is == 2 || b.is == 1 || x == b.x) return false;
		// cout << "C " << x << " " << b.x << "\n"; cout.flush();
		// ull t; cin >> t; return (t == x);
        return x < b.x;
	}
}c[N];

#define ls k << 1
#define rs k << 1 | 1

struct segtree
{
	int l[N << 2], r[N << 2];
	info t[N << 2];
	void build(int k, int L, int R)
	{
		l[k] = L, r[k] = R;
		if (L == R) return t[k] = c[L], void();
		int mid = (L + R) >> 1;
		build(ls, L, mid); build(rs, mid + 1, R);
		t[k] = t[ls] + t[rs];
	}
	
	void change(int k, int x, ull d)
	{
		if (l[k] == r[k]) return t[k] = info(d, 0), void();
		int mid = (l[k] + r[k]) >> 1;
		if (x <= mid) change(ls, x, d); else change(rs, x, d);
		t[k] = t[ls] + t[rs];
	}
}T1[8], T2[8];

info res;
vector<ull> ans;
void Solve(int k1, int k2, int p1, int p2, info val1, info val2)
{
    if (T1[p1].l[k1] == T1[p1].r[k1]) return res = val1 < val2 ? val2 : val1, void();
	info nw1 = val1 + T1[p1].t[k1 << 1], nw2 = val2 + T2[p2].t[k2 << 1];
	if (nw1 < nw2) Solve(k1 << 1 | 1, k2 << 1, p1, p2, nw1, val2);
	else Solve(k1 << 1, k2 << 1 | 1, p1, p2, val1, nw2);
}

int rev[N];
int op[maxn], typ[maxn], k[maxn];
ull vl[maxn];

int main()
{
	int n, q, B;
	cin >> n >> q >> B;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];
	for (int i = 1; i <= q; i++)
	{
		cin >> op[i];
		if (op[i] == 1) cin >> typ[i] >> k[i] >> vl[i];
		else cin >> k[i];
	}
	
	for (int i = 1; i < N; i++) rev[i] = rev[i >> 1] >> 1 | ((i & 1) << (B - 1));
	
    if (B <= 6)
    {
        int cnt = 0;
        for (int i = 0; i < (1 << B); i++)
            if (i == rev[i]) X[cnt++] = (1 << B) - 1 - i;
    }
	else if (B <= 12)
	{
        int cnt = 0;
        for (int i = 0; i < 8; i++) X[i] = (i ^ 7) + rev[i ^ 7];
        for (int i = 0; i < (1 << (B - 3)); i += 8)
            if (i == rev[i]) Y[cnt++] = (1 << (B - 3)) - 8 - i;
	}
    else
    {
        for (int i = 0; i < 8; i++) X[i] = (i ^ 7) + rev[i ^ 7];
        for (int i = 0; i < 8; i++) Y[i] = ((i ^ 7) << 3) + rev[(i ^ 7) << 3] + (1 << (B - 6)) - (1 << 6);
    }
    for (int i = 0; i < 8; i++)
        if (X[i] + N - (1 << B) >= 0) X[i] += N - (1 << B);

    for (int i = 0; i < 8; i++)
    {
        for (int j = 1; j <= X[i]; j++) c[j] = info(0, 1);
        for (int j = X[i] + 1; j <= min(N, X[i] + n); j++) c[j] = info(a[j - X[i]], 0);
        for (int j = X[i] + n + 1; j <= N; j++) c[j] = info(0, 2);
        T1[i].build(1, 1, N);
        for (int j = 1; j <= Y[i]; j++) c[j] = info(0, 1);
        for (int j = Y[i] + 1; j <= min(N, Y[i] + n); j++) c[j] = info(b[j - Y[i]], 0);
        for (int j = Y[i] + n + 1; j <= N; j++) c[j] = info(0, 2);
        T2[i].build(1, 1, N);
    }
	
	for (int i = 1; i <= q; i++)
		if (op[i] == 1)
		{
			if (typ[i] == 1)
			{
				for (int j = 0; j < 8; j++)
					if (X[j] + k[i] <= N) T1[j].change(1, X[j] + k[i], vl[i]);
			}
            else
            {
                for (int j = 0; j < 8; j++)
                    if (Y[j] + k[i] <= N) T2[j].change(1, Y[j] + k[i], vl[i]);
            }
		}
		else
		{
			bool Fl = 0;
			for (int p = 0; p < 8 && !Fl; p++)
				for (int q = 0; q < 8 && !Fl; q++)
					if (X[p] + Y[q] + k[i] == N - 1)
                        Fl = 1, Solve(1, 1, p, q, info(0, 1), info(0, 1)), ans.emplace_back(res.x);
		}
	cout << "! " << ans.size() << "\n";
	for (ull val : ans) cout << val << " ";
	return 0;
}