牛牛有一个数列，数列有n个数,第i个数记为ai同时。牛牛有两个数 s,w
，现在牛牛想要问你几个问题，每个问题都对应一个区间 [l,r]
定义一个点k (k ∈ [l,r])
当i ∈[l,r]时, ai xor s ≤ ak xor s 恒成立
注：如果有多个k满足上式，那么k取最靠左的那一个
定义一个数S
区间[l,r]除去点k的ai的异或和
即 S=al xor al+1 xor al+2.... xor ar (ak不会参加异或)
牛牛想要你输出 S xor W 的最大值 (W ∈[0,w])
。牛牛会问你q次这样的问题
提示：题目描述中的变量区分大小写
第一行包含四个整数n,q,s,w。
接下来一行有n个数，ai。
接下来q行，每行两个整数 l r。
对于每次询问输出一行
5 2 3 4
6 9 8 16 7
1 5
2 44
5
第一次询问是1-5，此时区间内与3异或出的值最大的数是16，除去16，这个区间异或和为0，0与1-4中的数异或能得到的最大的数是4.（0 xor 4 = 4）故输出4.
第二次询问是2-4，此时区间内与3异或出的值最大的数是16，除去16，这个区间异或和为1，1与1-4中的数异或能得到的最大的数是5.（1 xor 4 = 5）故输出5.
备注:
对于30%的数据：0≤n,q≤10^3
对于100%的数据：0≤n,q≤10^6,ai,s,w≤2^30 − 1
时间限制：2s