题目描述

给定一个整数 $m$，一个长度为 $n$ 的非负整数数组 $a$，以及 $q$ 个形如 $l_i$, $r_i$ 的查询。数组 $a$ 的所有元素都小于 $2^m$。

定义函数 $f_i(x) = \min_{j \in [l_i, r_i]} (a_j \oplus x)$，其中 $\oplus$ 表示按位异或运算。对于每个查询，你需要找到 $\max_{x \in \{0, 1, \ldots, 2^m-1\}} f_i(x)$ 的值。

非负整数 $a$ 和 $b$ 的按位异或 $(a \oplus b)$ 是一个非负整数，其二进制表示中某一位为 1 当且仅当 $a$ 和 $b$ 在该位的二进制值不同。例如，$3_{10} \oplus 5_{10} = 0011_{2} \oplus 0101_{2} = 0110_{2} = 6_{10}$。

输入格式

第一行包含三个整数 $n$, $q$, $m$（$1 \le n \le 10^5$, $1 \le q \le 5 \cdot 10^5$, $1 \le m \le 50$），分别表示数组长度、查询数量和数组元素的位数限制。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i < 2^m$），表示数组的元素。

接下来的 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$），表示第 $i$ 个查询的参数。

输出格式

对于每个查询，输出一行一个整数——$\max_{x \in \{0, 1, \ldots, 2^m-1\}} f_i(x)$ 的值。

输入输出样例 #1

输入 #1

5 5 3
1 3 2 7 1
1 5
2 3
3 4
1 3
1 1

输出 #1

3
6
3
5
7

说明/提示

第一个查询的分析：

$f_1(0)=\min(1 \oplus 0, 3 \oplus 0, 2 \oplus 0, 7 \oplus 0, 1 \oplus 0)=\min(1, 3, 2, 7, 1)=1$

$f_1(1)=\min(1 \oplus 1, 3 \oplus 1, 2 \oplus 1, 7 \oplus 1, 1 \oplus 1)=\min(0, 2, 3, 6, 0)=0$

$f_1(2)=\min(1 \oplus 2, 3 \oplus 2, 2 \oplus 2, 7 \oplus 2, 1 \oplus 2)=\min(3, 1, 0, 5, 3)=0$

$f_1(3)=\min(1 \oplus 3, 3 \oplus 3, 2 \oplus 3, 7 \oplus 3, 1 \oplus 3)=\min(2, 0, 1, 4, 2)=0$

$f_1(4)=\min(1 \oplus 4, 3 \oplus 4, 2 \oplus 4, 7 \oplus 4, 1 \oplus 4)=\min(5, 7, 6, 3, 5)=3$

$f_1(5)=\min(1 \oplus 5, 3 \oplus 5, 2 \oplus 5, 7 \oplus 5, 1 \oplus 5)=\min(4, 6, 7, 2, 4)=2$

$f_1(6)=\min(1 \oplus 6, 3 \oplus 6, 2 \oplus 6, 7 \oplus 6, 1 \oplus 6)=\min(7, 5, 4, 1, 7)=1$

$f_1(7)=\min(1 \oplus 7, 3 \oplus 7, 2 \oplus 7, 7 \oplus 7, 1 \oplus 7)=\min(6, 4, 5, 0, 6)=0$

该查询的答案为 $\max_{x \in \{0, 1, \ldots, 2^3-1\}} f_1(x) = \max(1, 0, 0, 0, 3, 2, 1, 0) = 3$。

评分标准

• （$4$ 分）：$n \le 100$，$q \le 100$，$m \le 10$；
• （$17$ 分）：$q=1$，$l_1=1$，$r_1=n$；
• （$16$ 分）：$q \le 2 \cdot 10^5$；$a_i \le a_{i+1}$（$1 \le i < n$）；
• （$17$ 分）：$n \le 10^4$，$q \le 10^4$；
• （$26$ 分）：$n \le 5 \cdot 10^4$，$m \le 30$；
• （$20$ 分）：无额外限制。