Description

凡斯和德莱姆告诉彩梦，一个非负整数序列的 $\text{mex}$ 为最小没有出现过的非负整数，例如 $\text{mex}([0, 1, 3]) = 2$。

彩梦定义一个非负整数序列的 $\text{xormex}$ 为将每个元素异或一个相同非负整数后，序列 $\text{mex}$ 的最大值，例如 $\text{xormex}([8, 9, 11]) = \text{mex}([8 \oplus 9, 9 \oplus 9, 11 \oplus 9]) = \text{mex}([1, 0, 2]) = 3$。

给定长度为 $2^n$ 的序列 $a$ 和 $m$ 次询问，每次询问给定两个整数 $l, r$，彩梦想知道以下两个问题的答案：

• 子区间 $[a_l, a_{l+1}, \cdots, a_r]$ 的 $\text{xormex}$。
• 对于所有 $l \leq x \leq y \leq r$，子区间 $[a_x, a_{x+1}, \cdots, a_y]$ 的 $\text{xormex}$ 的和。

Input Format

第一行输入三个整数 $n, m, o$。

第二行输入 $2^n$ 个整数 $a_i$。

接下来 $m$ 行，每行输入两个整数 $l, r$。

Output Format

输出 $m$ 行，每行包含一个整数，代表每个询问的答案。

如果 $o = 1$，你需要输出第一个问题的答案。

如果 $o = 2$，你需要输出第二个问题的答案。

2 4 1
3 2 0 1
1 3
2 3
1 2
1 4

3
1
2
4

3 5 2
0 4 6 7 5 2 1 3
1 8
3 5
2 6
3 7
1 4

93
9
29
22
15

Hint

附加样例 3~5

见下发文件的 desive3~5.in 与 desive3~5.ans。

这些样例分别满足子任务 1,2,6 的限制。

样例解释

对于第一个询问，$\text{xormex}([3, 2, 0]) = \text{mex}([3 \oplus 2, 2 \oplus 2, 0 \oplus 2]) = \text{mex}([1, 0, 2]) = 3$。

对于第二个询问，$\text{xormex}([2, 0]) = \text{mex}([2, 0]) = 1$。

对于第三个询问，$\text{xormex}([3, 2]) = \text{mex}([3 \oplus 3, 2 \oplus 3]) = \text{mex}([0, 1]) = 2$。

对于第四个询问，$\text{xormex}([3, 2, 0, 1]) = \text{mex}([3, 2, 0, 1]) = 4$。

数据范围

对于所有数据，$1 \leq n \leq 18$，$1 \leq m \leq 10^6$，$0 \leq a_i < 2^n$，$1 \leq l \leq r \leq 2^n$。

• Subtask 1（7 pts）：$n \leq 6$, $m \leq 10^3$.
• Subtask 2（15 pts）：$n \leq 12$, $m \leq 5 \times 10^4$.
• Subtask 3（13 pts）：$n \leq 16$, $m \leq 10^5$, $o = 1$.
• Subtask 4（16 pts）：$n \leq 17$, $m \leq 5 \times 10^5$, $o = 1$.
• Subtask 5（10 pts）：$o = 1$.
• Subtask 6（12 pts）：$n \leq 17$, $m \leq 5 \times 10^5$, $a_i$ 两两不同.
• Subtask 7（5 pts）：$a_i$ 两两不同.
• Subtask 8（14 pts）：$n \leq 17$, $m \leq 5 \times 10^5$.
• Subtask 9（8 pts）：无特殊限制.

后记

将她从生与死的边界打捞的……是良方，还是奇迹？抑或是友谊？

……或许，都是吧。

当她的梦境第一回被光芒点亮的时候，她看见了她的朋友们为了保护她而奋不顾身的样子。 她确信，自己也会在它们遇见危险的时候这么做。 她一定会保护好它们——当然也包括她刚结识的那位新朋友。

当她们终于能彼此释怀，能够从容地分享自己所走过的路，讲述所遇到过的来自陌生人的善意的时候……

彩梦不禁笑了，她的嘴翘起了一个漂亮的弧度。 能自在释怀地笑，真是幸运至极呢。