题目背景

它的确很特殊，很引人注目，但异象从来都不特别。

它们终归只是错误而已：是人心里脆弱部分的回响，有着人心愿破碎时的音色。

就其本质而言，比起那颗心所渴望的，它们更接近那颗心本来的样子：一点也不特别， 但平凡同样可以拥有毁灭性的力量。

命运本身并不会带来缺陷，这样的痛苦也无法通过希望或命运的丝线挣脱——在这点上， 这枚曾经一度拥有摧毁性的强大力量的碎片能最终被找到并带回，和其他被寻得的碎片一样， 跟渴望没有一点关系。

大多时候，寻得异象的过程更像是追寻风的足迹，来无影去无踪，没有逻辑，也无需理由。

这片陈旧的，残缺的，容纳着悲伤和痛苦的躯壳…… 它能被找到，实在算不上什么奇迹，而仅仅是因为想要寻找它的人，心中都有着纯粹至极的情感，如此而已。 而这片连接起事物的存在，此时终于来到了她的唇齿之间。

题目描述

凡斯和德莱姆告诉彩梦，一个非负整数序列的 $\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$，你需要输出第二个问题的答案。

样例 1

样例 1 输入

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

样例 1 输出

3
1
2
4

样例 2

样例 2 输入

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

样例 2 输出

93
9
29
22
15

附加样例 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\le n\le 18$，$1\le m\le 10^6$，$0\le a_i < 2^n$，$1\le l\le r\le 2^n$。

本题共 37 个测试点，子任务之间存在依赖关系，请不要频繁提交。

后记

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

……或许，都是吧。

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

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

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