非常巧妙的技巧。

首先 $f(x_i) \cdot f(x_{i+1}) \leq 0$ 实际上是需求异号。

我们思考如何找到两个异号（不一定相邻）的 $f(x_p)$。

比较直观的，我们可以想到，由于 $f(x_p) = (a \oplus x_p) - b$。

故我们可以尝试找到最小的和最大的 $a \oplus x_p$，这是 01Trie 的经典问题。

判断它们是否异号，如果同号，那么所有的 $f(x_p)$ 都同号。

否则，我们找到了一对异号的点，我们考虑相邻的条件。

对于这样的问题，我们有一个经典技巧。

考虑二分，记上述点对为左右两端点，我们取中点。由于左右两端点异号，那么中点一定与其中一个异号，故每一次我们都可以将区间大小折半。

时间复杂度 $O(q\log_n)$。

注意到 $f(x_p) = 0$ 的情况，思考一下发现并没有问题。

注意 $f(x_p)$ 全部相等的情况，初始的端点不要求成同一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6;
const int maxk=30;
const int maxm=maxn*maxk;
int n,q;
int a[maxn+5];
int tot=1;
int ch[maxm+5][2];
inline void Insert(int x,int id){
    int u=1;
    for(int i=maxk-1,t;i>=0;i--){
        t=(x>>i)&1;
        if(!ch[u][t]) ch[u][t]=++tot;
        u=ch[u][t];
    }
    if(!ch[u][0]) ch[u][0]=id;
    ch[u][1]=id;
}
inline int Querymn(int x){
    int u=1;
    for(int i=maxk-1,t;i>=0;i--){
        t=(x>>i)&1;
        if(ch[u][t]) u=ch[u][t];
        else u=ch[u][!t];
    }
    return ch[u][0];
}
inline int Querymx(int x){
    int u=1;
    for(int i=maxk-1,t;i>=0;i--){
        t=(x>>i)&1;
        if(ch[u][!t]) u=ch[u][!t];
        else u=ch[u][t];
    }
    return ch[u][1];
}
inline int Calc(int p,int x,int y){
    if((a[p]^x)>y) return 1;
    else if((a[p]^x)<y) return -1;
    else return 0;
}
namespace IO{
    short st[15],tp;
    inline int Read(){
        int res=0;char ch=getchar();
        while(ch<'0'||'9'<ch) ch=getchar();
        while('0'<=ch&&ch<='9')
            res=(res<<1)+(res<<3)+ch-'0',ch=getchar();
        return res;
    }
    inline void Write(int x){
        while(x) st[++tp]=x%10,x/=10;
        for(int i=tp;i;i--) putchar('0'+st[i]);
        tp=0;
        putchar('\n');
    }
}
using IO::Read;
using IO::Write;
signed main(){
    freopen("fun.in","r",stdin);
    freopen("fun.out","w",stdout);
    n=Read(),q=Read();
    for(int i=1;i<=n;i++){
        a[i]=Read();
        Insert(a[i],i);
    }
    int x,y,l,r,p;
    while(q--){
        x=Read(),y=Read();
        l=Querymn(x),r=Querymx(x);
        if(Calc(l,x,y)*Calc(r,x,y)>0) puts("-1");
        else{
            if(l>r) swap(l,r);
            while(r-l>1){
                p=(l+r)/2;
                if(Calc(l,x,y)*Calc(p,x,y)<=0) r=p;
                else l=p;
            }
            Write(l);
        }
    }
    return 0;
}