题目描述

题目译自 Ukrainian Olympiads in Informatics 2023 Stage 4 Day2 T4. Масив і XOR

给定一个整数 $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)$，表示数组 $a$ 的元素。

接下来的 $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)$ 的值。

5 5 3
1 3 2 7 1
1 5
2 3
3 4
1 3
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$。

数据范围与提示

详细子任务附加限制及分值如下表所示：