问题描述

又到了小机器人维修时间！

由于工作损耗，小机器人可能会偏移了正常的行为设定，我们用 $b_i$ 表示每个小机器人的偏移值。你的任务是将所有小机器人恢复正常（即将所有偏移值变为 $0$）。你有一把脉冲枪来完成这项任务，脉冲枪初始脉冲值 $x = 0$，单位时间内，你可以进行如下操作之一：

• 将 $x$ 增加 $1$。
• 对一个小机器人进行施加异或脉冲，即选择一个 $i$，令 $b_i \leftarrow b_i \oplus x$。

其中 $\oplus$ 表示二进制下的异或运算。

现在，给定长度为 $n$ 的序列 $a_i$ 表示小机器人的偏移值，多次询问修理区间 $[l,r]$ 中所有小机器人所需花费的最少时间。

输入格式

第一行三个整数 $n,Q,t$，分别表示小机器人数量、询问次数、是否强制在线。

第二行共 $n$ 个正整数，分别表示每个小机器人的偏移值 $a_i$。

接下来 $Q$ 行，每行两个整数 $l'_i,r'_i$ 代表一次询问。当 $t=1$ 时 $l_i = l'_i,r_i = r'_i$。当 $t = 2$ 时，$l_i = \min(l'_i \oplus lst,r'_i \oplus lst),r_i = \max(l'_i \oplus lst,r'_i \oplus lst)$，其中 $lst$ 表示上一次询问的答案（初始为 $0$）。

输出格式

共 $Q$ 行，第 $i$ 行表示第 $i$ 次修理所需的最少时间。

输入样例

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

输出样例

9
11
12
14
12
6

数据范围

对于 $100\%$ 的数据，$1\leq n,Q \leq 2 \times 10^5,1\le l_i \le r_i\le n,1\le a_i < 2^{60}$。

特殊性质 A: $\forall i \in [1,n)$，$a_i \le a_{i+1}$。

特殊性质 B: $\forall i \in [1,Q]$，$l_i = 1, r_i = i$。