#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, q;
int a[500100];
int best[500100];
int seg[5001000];
int lazy[5001000];
int sq[500100];
int eq[500100];
vector<pair<int, int> > qrs;
vector<pair<int, int> > sweep;
const int MAX_CHAR = 2;
struct trie {
trie* child[MAX_CHAR];
int maxi;
trie() {
memset(child, 0, sizeof(child));
maxi = -1;
}
void insert(int a, int idx, int length = 30){
maxi = max(maxi, idx);
if (length == -1) return;
int d = a / (1 << length);
if (child[d] == 0) child[d] = new trie();
child[d]->insert(a % (1 << length), idx, length - 1);
}
int query(int a, int length = 30){
if (length == -1) return maxi;
int d = a / (1 << length);
int dm = (m % (1 << (length + 1))) / (1 << length);
int ans = -1;
if (dm == 0 && child[1 - d] != 0) ans = child[1 - d]->maxi;
if (dm == 0 && child[d] != 0) ans = max(ans, child[d]->query(a % (1 << length), length - 1));
else if (dm == 1 && child[1 - d] != 0) ans = max(ans, child[1 - d]->query(a % (1 << length), length - 1));
return ans;
}
};
void init(trie *cur)
{
if(cur == 0) return;
for (int i = 0; i < MAX_CHAR; i++)
if (cur->child[i] != NULL)
init(cur->child[i]);
delete cur;
}
void clear(){
for (int i = 0; i <= n; i++) best[i] = 1e9;
for (int i = 0; i <= q * 5; i++) seg[i] = -1, lazy[i] = 1e9;
sweep.clear();
qrs.clear();
}
void pushLazy(int p){
if (lazy[p] != 1e9){
lazy[p * 2] = min(lazy[p * 2], lazy[p]);
lazy[p * 2 + 1] = min(lazy[p * 2 + 1], lazy[p]);
seg[p] = min(seg[p], lazy[p]);
lazy[p] = 1e9;
}
}
void update(int i, int j, int val, int p = 1, int L = 0, int R = q - 1){
pushLazy(p);
if (i > R || j < L) return;
if (L >= i && R <= j){
lazy[p] = val;
pushLazy(p);
return;
}
int midi = (L + R) / 2;
update(i, j, val, p * 2, L, midi);
update(i, j, val, p * 2 + 1, midi + 1, R);
seg[p] = min(seg[p * 2], seg[p * 2 + 1]);
}
void turnOn(int i, int p = 1, int L = 0, int R = q - 1){
pushLazy(p);
if (L == R){
seg[p] = 1e9;
return;
}
int midi = (L + R) / 2;
if (i <= midi) turnOn(i, p * 2, L, midi);
else turnOn(i, p * 2 + 1, midi + 1, R);
seg[p] = min(seg[p * 2], seg[p * 2 + 1]);
}
int query(int i, int p = 1, int L = 0, int R = q - 1){
pushLazy(p);
if (L == R) return seg[p];
int midi = (L + R) / 2;
if (i <= midi) return query(i, p * 2, L, midi);
return query(i, p * 2 + 1, midi + 1, R);
}
void calcBest(){
trie* root = new trie();
root->insert(a[0], 0);
for (int i = 1; i <= n; i++){
int s = root->query(a[i]);
if(s != -1) best[s + 1] = min(i, best[s + 1]);
root->insert(a[i], i);
}
init(root);
}
void calcSweep(){
for (int i = 0; i < (int)sweep.size(); i++){
int fir = sweep[i].first, sec = sweep[i].second;
if (sec != 1e9){
int idx = lower_bound(qrs.begin(), qrs.end(), make_pair(sec, fir)) - qrs.begin();
turnOn(idx);
}
else{
if (best[fir] == 1e9) continue;
int length = best[fir] - fir + 1;
int idx = lower_bound(qrs.begin(), qrs.end(), make_pair(best[fir], -1)) - qrs.begin();
update(idx, q - 1, length);
}
}
}
int main() {
int t;
scanf("%d",&t);
while (t--){
scanf("%d %d %d",&n,&m,&q);
clear();
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) a[i] ^= a[i - 1];
calcBest();
for (int i = 0; i < q; i++){
scanf("%d %d",sq+i,eq+i);
qrs.push_back(make_pair(eq[i], sq[i]));
sweep.push_back(make_pair(sq[i], eq[i]));
}
for (int i = 1; i <= n; i++) sweep.push_back(make_pair(i, 1e9));
sort(sweep.begin(), sweep.end());
sort(qrs.begin(), qrs.end());
calcSweep();
for (int i = 0; i < q; i++){
int idx = lower_bound(qrs.begin(), qrs.end(), make_pair(eq[i], sq[i])) - qrs.begin();
int ans = query(idx);
if (ans > 1e8) ans = -1;
printf("%d\n",ans);
}
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdHlwZWRlZiBsb25nIGxvbmcgbGw7CgppbnQgbiwgbSwgcTsKaW50IGFbNTAwMTAwXTsKaW50IGJlc3RbNTAwMTAwXTsKaW50IHNlZ1s1MDAxMDAwXTsKaW50IGxhenlbNTAwMTAwMF07CmludCBzcVs1MDAxMDBdOwppbnQgZXFbNTAwMTAwXTsKdmVjdG9yPHBhaXI8aW50LCBpbnQ+ID4gcXJzOwp2ZWN0b3I8cGFpcjxpbnQsIGludD4gPiBzd2VlcDsKCmNvbnN0IGludCBNQVhfQ0hBUiA9IDI7CnN0cnVjdCB0cmllIHsKCXRyaWUqIGNoaWxkW01BWF9DSEFSXTsKCWludCBtYXhpOwoKCXRyaWUoKSB7CgkJbWVtc2V0KGNoaWxkLCAwLCBzaXplb2YoY2hpbGQpKTsKCQltYXhpID0gLTE7Cgl9CgoJdm9pZCBpbnNlcnQoaW50IGEsIGludCBpZHgsIGludCBsZW5ndGggPSAzMCl7CgkJbWF4aSA9IG1heChtYXhpLCBpZHgpOwoJCWlmIChsZW5ndGggPT0gLTEpIHJldHVybjsKCgkJaW50IGQgPSBhIC8gKDEgPDwgbGVuZ3RoKTsKCQlpZiAoY2hpbGRbZF0gPT0gMCkgY2hpbGRbZF0gPSBuZXcgdHJpZSgpOwoJCWNoaWxkW2RdLT5pbnNlcnQoYSAlICgxIDw8IGxlbmd0aCksIGlkeCwgbGVuZ3RoIC0gMSk7Cgl9CgoJaW50IHF1ZXJ5KGludCBhLCBpbnQgbGVuZ3RoID0gMzApewoJCWlmIChsZW5ndGggPT0gLTEpIHJldHVybiBtYXhpOwoKCQlpbnQgZCA9IGEgLyAoMSA8PCBsZW5ndGgpOwoJCWludCBkbSA9IChtICUgKDEgPDwgKGxlbmd0aCArIDEpKSkgLyAoMSA8PCBsZW5ndGgpOwoJCWludCBhbnMgPSAtMTsKCQlpZiAoZG0gPT0gMCAmJiBjaGlsZFsxIC0gZF0gIT0gMCkgYW5zID0gY2hpbGRbMSAtIGRdLT5tYXhpOwoJCWlmIChkbSA9PSAwICYmIGNoaWxkW2RdICE9IDApIGFucyA9IG1heChhbnMsIGNoaWxkW2RdLT5xdWVyeShhICUgKDEgPDwgbGVuZ3RoKSwgbGVuZ3RoIC0gMSkpOwoJCWVsc2UgaWYgKGRtID09IDEgJiYgY2hpbGRbMSAtIGRdICE9IDApIGFucyA9IG1heChhbnMsIGNoaWxkWzEgLSBkXS0+cXVlcnkoYSAlICgxIDw8IGxlbmd0aCksIGxlbmd0aCAtIDEpKTsKCQlyZXR1cm4gYW5zOwoJfQp9OwoKdm9pZCBpbml0KHRyaWUgKmN1cikKewoJaWYoY3VyID09IDApIHJldHVybjsKCWZvciAoaW50IGkgPSAwOyBpIDwgTUFYX0NIQVI7IGkrKykKCWlmIChjdXItPmNoaWxkW2ldICE9IE5VTEwpCgkJaW5pdChjdXItPmNoaWxkW2ldKTsKCWRlbGV0ZSBjdXI7Cn0KCnZvaWQgY2xlYXIoKXsKCWZvciAoaW50IGkgPSAwOyBpIDw9IG47IGkrKykgYmVzdFtpXSA9IDFlOTsKCWZvciAoaW50IGkgPSAwOyBpIDw9IHEgKiA1OyBpKyspIHNlZ1tpXSA9IC0xLCBsYXp5W2ldID0gMWU5OwoJc3dlZXAuY2xlYXIoKTsKCXFycy5jbGVhcigpOwp9Cgp2b2lkIHB1c2hMYXp5KGludCBwKXsKCWlmIChsYXp5W3BdICE9IDFlOSl7CgkJbGF6eVtwICogMl0gPSBtaW4obGF6eVtwICogMl0sIGxhenlbcF0pOwoJCWxhenlbcCAqIDIgKyAxXSA9IG1pbihsYXp5W3AgKiAyICsgMV0sIGxhenlbcF0pOwoJCXNlZ1twXSA9IG1pbihzZWdbcF0sIGxhenlbcF0pOwoJCWxhenlbcF0gPSAxZTk7Cgl9Cn0KCnZvaWQgdXBkYXRlKGludCBpLCBpbnQgaiwgaW50IHZhbCwgaW50IHAgPSAxLCBpbnQgTCA9IDAsIGludCBSID0gcSAtIDEpewoJcHVzaExhenkocCk7CglpZiAoaSA+IFIgfHwgaiA8IEwpIHJldHVybjsKCWlmIChMID49IGkgJiYgUiA8PSBqKXsKCQlsYXp5W3BdID0gdmFsOwoJCXB1c2hMYXp5KHApOwoJCXJldHVybjsKCX0KCglpbnQgbWlkaSA9IChMICsgUikgLyAyOwoJdXBkYXRlKGksIGosIHZhbCwgcCAqIDIsIEwsIG1pZGkpOwoJdXBkYXRlKGksIGosIHZhbCwgcCAqIDIgKyAxLCBtaWRpICsgMSwgUik7CglzZWdbcF0gPSBtaW4oc2VnW3AgKiAyXSwgc2VnW3AgKiAyICsgMV0pOwp9Cgp2b2lkIHR1cm5PbihpbnQgaSwgaW50IHAgPSAxLCBpbnQgTCA9IDAsIGludCBSID0gcSAtIDEpewoJcHVzaExhenkocCk7CglpZiAoTCA9PSBSKXsKCQlzZWdbcF0gPSAxZTk7CgkJcmV0dXJuOwoJfQoKCWludCBtaWRpID0gKEwgKyBSKSAvIDI7CglpZiAoaSA8PSBtaWRpKSB0dXJuT24oaSwgcCAqIDIsIEwsIG1pZGkpOwoJZWxzZSB0dXJuT24oaSwgcCAqIDIgKyAxLCBtaWRpICsgMSwgUik7CglzZWdbcF0gPSBtaW4oc2VnW3AgKiAyXSwgc2VnW3AgKiAyICsgMV0pOwp9CgppbnQgcXVlcnkoaW50IGksIGludCBwID0gMSwgaW50IEwgPSAwLCBpbnQgUiA9IHEgLSAxKXsKCXB1c2hMYXp5KHApOwoJaWYgKEwgPT0gUikgcmV0dXJuIHNlZ1twXTsKCglpbnQgbWlkaSA9IChMICsgUikgLyAyOwoJaWYgKGkgPD0gbWlkaSkgcmV0dXJuIHF1ZXJ5KGksIHAgKiAyLCBMLCBtaWRpKTsKCXJldHVybiBxdWVyeShpLCBwICogMiArIDEsIG1pZGkgKyAxLCBSKTsKfQoKdm9pZCBjYWxjQmVzdCgpewoJdHJpZSogcm9vdCA9IG5ldyB0cmllKCk7Cglyb290LT5pbnNlcnQoYVswXSwgMCk7Cglmb3IgKGludCBpID0gMTsgaSA8PSBuOyBpKyspewoJCWludCBzID0gcm9vdC0+cXVlcnkoYVtpXSk7CgkJaWYocyAhPSAtMSkgYmVzdFtzICsgMV0gPSBtaW4oaSwgYmVzdFtzICsgMV0pOwoJCXJvb3QtPmluc2VydChhW2ldLCBpKTsKCX0KCWluaXQocm9vdCk7Cn0KCnZvaWQgY2FsY1N3ZWVwKCl7Cglmb3IgKGludCBpID0gMDsgaSA8IChpbnQpc3dlZXAuc2l6ZSgpOyBpKyspewoJCWludCBmaXIgPSBzd2VlcFtpXS5maXJzdCwgc2VjID0gc3dlZXBbaV0uc2Vjb25kOwoJCWlmIChzZWMgIT0gMWU5KXsKCQkJaW50IGlkeCA9IGxvd2VyX2JvdW5kKHFycy5iZWdpbigpLCBxcnMuZW5kKCksIG1ha2VfcGFpcihzZWMsIGZpcikpIC0gcXJzLmJlZ2luKCk7CgkJCXR1cm5PbihpZHgpOwoJCX0KCQllbHNlewoJCQlpZiAoYmVzdFtmaXJdID09IDFlOSkgY29udGludWU7CgkJCWludCBsZW5ndGggPSBiZXN0W2Zpcl0gLSBmaXIgKyAxOwoJCQlpbnQgaWR4ID0gbG93ZXJfYm91bmQocXJzLmJlZ2luKCksIHFycy5lbmQoKSwgbWFrZV9wYWlyKGJlc3RbZmlyXSwgLTEpKSAtIHFycy5iZWdpbigpOwoJCQl1cGRhdGUoaWR4LCBxIC0gMSwgbGVuZ3RoKTsKCQl9Cgl9Cn0KCmludCBtYWluKCkgewoKCWludCB0OyAKCXNjYW5mKCIlZCIsJnQpOwoJd2hpbGUgKHQtLSl7CgkJc2NhbmYoIiVkICVkICVkIiwmbiwmbSwmcSk7CgkJY2xlYXIoKTsKCQlmb3IgKGludCBpID0gMTsgaSA8PSBuOyBpKyspIGNpbiA+PiBhW2ldOwoJCWZvciAoaW50IGkgPSAxOyBpIDw9IG47IGkrKykgYVtpXSBePSBhW2kgLSAxXTsKCQljYWxjQmVzdCgpOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgcTsgaSsrKXsKCQkJc2NhbmYoIiVkICVkIixzcStpLGVxK2kpOwoJCQlxcnMucHVzaF9iYWNrKG1ha2VfcGFpcihlcVtpXSwgc3FbaV0pKTsKCQkJc3dlZXAucHVzaF9iYWNrKG1ha2VfcGFpcihzcVtpXSwgZXFbaV0pKTsKCQl9CgkJZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKSBzd2VlcC5wdXNoX2JhY2sobWFrZV9wYWlyKGksIDFlOSkpOwoJCXNvcnQoc3dlZXAuYmVnaW4oKSwgc3dlZXAuZW5kKCkpOwoJCXNvcnQocXJzLmJlZ2luKCksIHFycy5lbmQoKSk7CgkJY2FsY1N3ZWVwKCk7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCBxOyBpKyspewoJCQlpbnQgaWR4ID0gbG93ZXJfYm91bmQocXJzLmJlZ2luKCksIHFycy5lbmQoKSwgbWFrZV9wYWlyKGVxW2ldLCBzcVtpXSkpIC0gcXJzLmJlZ2luKCk7CgkJCWludCBhbnMgPSBxdWVyeShpZHgpOwoJCQlpZiAoYW5zID4gMWU4KSBhbnMgPSAtMTsKCQkJcHJpbnRmKCIlZFxuIixhbnMpOwoJCX0KCX0KCglyZXR1cm4gMDsKfQ==