P12478 [集训队互测 2024] Désive

**由于评测机性能差距，本题时限增加了 1 秒。** 它的确很特殊，很引人注目，但异象从来都不特别。 它们终归只是错误而已：是人心里脆弱部分的回响，有着人心愿破碎时的音色。 就其本质而言，比起那颗心所渴望的，它们更接近那颗心本来的样子：一点也不特别， 但平凡同样可以拥有毁灭性的力量。 命运本身并不会带来缺陷，这样的痛苦也无法通过希望或命运的丝线挣脱——在这点上， 这枚曾经一度拥有摧毁性的强大力量的碎片能最终被找到并带回，和其他被寻得的碎片一样， 跟渴望没有一点关系。 大多时候，寻得异象的过程更像是追寻风的足迹，来无影去无踪，没有逻辑，也无需理由。 这片陈旧的，残缺的，容纳着悲伤和痛苦的躯壳…… 它能被找到，实在算不上什么奇迹，而仅仅是因为想要寻找它的人，心中都有着纯粹至极的情感，如此而已。 而这片连接起事物的存在，此时终于来到了她的唇齿之间。

凡斯和德莱姆告诉彩梦，一个非负整数序列的 $\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}$ 的和。

第一行输入三个整数 $n, m, o$。 第二行输入 $2^n$ 个整数 $a_i$。 接下来 $m$ 行，每行输入两个整数 $l, r$。

输出 $m$ 行，每行包含一个整数，代表每个询问的答案。 如果 $o = 1$，你需要输出第一个问题的答案。 如果 $o = 2$，你需要输出第二个问题的答案。

### 附加样例 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）：无特殊限制. ### 后记 将她从生与死的边界打捞的……是良方，还是奇迹？抑或是友谊？ ……或许，都是吧。 当她的梦境第一回被光芒点亮的时候，她看见了她的朋友们为了保护她而奋不顾身的样子。 她确信，自己也会在它们遇见危险的时候这么做。 她一定会保护好它们——当然也包括她刚结识的那位新朋友。 当她们终于能彼此释怀，能够从容地分享自己所走过的路，讲述所遇到过的来自陌生人的善意的时候…… 彩梦不禁笑了，她的嘴翘起了一个漂亮的弧度。 能自在释怀地笑，真是幸运至极呢。