下面这份代码是 $O(n \log n \log V)$ 的。但是极限数据需要跑 20s。vector 常数有这个大吗？

#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;

const int N = 2e5 + 5;
const int inf = 1e9;

int T, n, q, V, a[N], b[N];

pii operator + (pii x, pii y) {
	return make_pair(max(x.fi, y.fi), x.se | y.se);
}

struct B {
	int ans;
	pii v;
	vector<pii> pre, suf;

	B(int va = 0, int vb = 0) {
		ans = vb >= V ? va : inf;
		v = make_pair(va, vb);
		pre.clear();
		suf.clear();
		pre.emplace_back(v);
		suf.emplace_back(v);
	}
} c[N * 4];

B operator + (B x, B y) {
	B res;
	res.ans = min(x.ans, y.ans);
	res.v = x.v + y.v;
	for (pii v : x.pre) {
		res.pre.emplace_back(v);
	}
	for (pii v : y.pre) {
		pii v_ = x.v + v;
		if (v_.se != res.pre.back().se) {
			res.pre.emplace_back(v_);
		}
	}
	for (pii v : y.suf) {
		res.suf.emplace_back(v);
	}
	for (pii v : x.suf) {
		pii v_ = v + y.v;
		if (v_.se != res.suf.back().se) {
			res.suf.emplace_back(v_);
		}
	}
	pii vy;
	for (int i = (int)x.suf.size() - 1, j = 0; i >= 0; i--) {
		pii vx = x.suf[i];
		while (j < y.pre.size() && (vx + vy).se < V) {
			vy = y.pre[j++];
		}
		if ((vx + vy).se >= V) {
			res.ans = min(res.ans, (vx + vy).fi);
		}
	}
	return res;
}

void build(int p, int l, int r) {
	if (l == r) {
		c[p] = B(a[l], b[l]);
		return;
	}
	int mid = l + r >> 1;
	build(p * 2, l, mid);
	build(p * 2 + 1, mid + 1, r);
	c[p] = c[p * 2] + c[p * 2 + 1];
}

void modify(int p, int l, int r, int x) {
	if (l == r) {
		c[p] = B(a[l], b[l]);
		return;
	}
	int mid = l + r >> 1;
	if (x <= mid) {
		modify(p * 2, l, mid, x);
	}
	else {
		modify(p * 2 + 1, mid + 1, r, x);
	}
	c[p] = c[p * 2] + c[p * 2 + 1];
}

B query(int p, int l, int r, int a, int b) {
	if (l >= a && r <= b) {
		return c[p];
	}
	int mid = l + r >> 1;
	if (b <= mid) {
		return query(p * 2, l, mid, a, b); 
	}
	if (a > mid) {
		return query(p * 2 + 1, mid + 1, r, a, b);
	}
	return query(p * 2, l, mid, a, b) + query(p * 2 + 1, mid + 1, r, a, b);
}

void work() {
	cin >> n >> V;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		cin >> b[i];
	}
	build(1, 1, n);
	cin >> q;
	for (int i = 1; i <= q; i++) {
		int op, x, y;
		cin >> op >> x >> y;
		if (op == 1) {
			b[x] = y;
			modify(1, 1, n, x);
		}
		else {
			B res = query(1, 1, n, x, y);
			cout << (res.ans == inf ? -1 : res.ans) << ' ';
		}
	}
	cout << '\n';
}

int main() {
	int st = clock();
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> T;
	while (T--) {
		work();
	}
	
	return 0;
}