牛牛的数列

题号：NC214574
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

牛牛有一个数列，数列有 $n$ 个数,第 $i$ 个数记为 $a_i$ 同时。牛牛有两个数 $s$ , $w$

，现在牛牛想要问你几个问题，每个问题都对应一个区间 $[l,r]$

定义一个点 $k$ ( $k$ $\in$ $[l,r]$ )

当i $\in$ $[l,r]$ 时, $a_i$ $xor$ $s$ $\le$ $a_k$ $xor$ $s$ 恒成立

注：如果有多个k满足上式，那么k取最靠左的那一个

定义一个数 $S$

区间 $[l,r]$ 除去点k的 $a_i$ 的异或和

即 $S$ = $a_{l}$ $xor$ $a_{l+1}$ $xor$ $a_{l+2}$ ...... $xor$ $a_r$ ( $a_k$ 不会参加异或)

牛牛想要你输出 $S$ $xor$ $W$ 的最大值 ( $W$ $\in$ $[0,w]$ )

。牛牛会问你 $q$ 次这样的问题

提示：题目描述中的变量区分大小写

输入描述:

第一行包含四个整数n,q,s,w。
接下来一行有n个数，。
接下来q行，每行两个整数 l r。

输出描述:

对于每次询问输出一行

示例1

输入

复制

输出

复制

4
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%的数据：。
对于%100%的数据：。