4. 硬币游戏

【题目描述】

快乐的 Alice 在和自己玩一个硬币游戏。

游戏过程如下：

Alice 找到一个序列 $A$，并且规定了一个常数 $k$，初始时 $k = 0$。

Alice 可以花费一枚硬币进行以下一种操作：

1. 选定一个位置 $i$，使得 $A_i$ 变成 $A_i \oplus k$。

2. 将 $k$ 加一。

Alice 将不断操作直到 $A$ 中所有元素都变成 0。

聪明的 Alice 一下就找到了最小的硬币花费，我们将其记作 $cost(A)$。

现在她想和你一起玩硬币游戏，她将给定一个长度为 $n$ 的序列 $A$，并且对你发起 $q$ 此挑战。

对于每次挑战，将给定一个区间 $[l,r]$，你需要快速求出 $cost(A_{[l, r]})$。

并且，为了加大难度，Alice 将每次查询都进行了加密，你只有回答出上一次查询的答案，她才会给出下一个查询。

【输入格式】

第一行三个整数 $n, q, k = 1/2$，表示序列长度，查询次数，查询类型。

接下来一行 $n$ 个整数表示序列 $A$。

接下来 $q$ 行，每行两个整数表示一次询问的区间 $[l, r]$。

记上一次查询的答案为 $lastans$，如果 $k = 2$，那么 $l, r$ 都应该异或上 $lastans$。

【输出格式】

每行一个整数表示一次查询的答案。

【样例输入】

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

【数据规模与约定】

数据按如下方式分组：

第一组 $8pts$：$k = 1$，对于所有的 $i$ 满足 $A_i = A_1$。

第二组 $12pts$：$k = 1$，对于所有的 $i \not= j$ 满足 $A_i \not= A_j$。

第三组 $8pts$：$k = 1$，满足 $q = 1, l_i = 1, r_i = n$。

第四组 $24pts$：$k = 1$, 满足 $q, n \le 1e4$。

第五组 $16pts$：$k = 1$，满足 $q, n \le 2e5$。

第六组 $32pts$：$k = 2$，满足 $q, n \le 2e5$。

对于所有数据点，有 $\forall a_i \le 2^{20}, q, n \le 2e5$。

大洋里