将子数组归零

这是一道交互题。

对于一个长度为 $m$ 的正整数数组 $b$，我们定义 $f(b)$ 如下：

• 初始时，设变量 $x = 0$；
• 花费 1 枚硬币，可以将 $x$ 的值增加 1；
• 花费 1 枚硬币，可以选择数组中的一个元素 $b_i$ ($1 \le i \le m$) 并将其替换为 $(b_i \oplus x)$，其中 $\oplus$ 表示按位异或运算；
• $f(b)$ 等于使数组 $b$ 中所有元素同时变为 0 所需的最少硬币数量。

非负整数 $a$ 和 $b$ 的按位异或运算 ($a \oplus b$) 等于一个非负整数，其二进制表示中，某一位为 1 当且仅当 $a$ 和 $b$ 在该位上的二进制值不同。例如，$3_{10} \oplus 5_{10} = 0011_2 \oplus 0101_2 = 0110_2 = 6_{10}$。

给定一个长度为 $n$ 的正整数数组 $a$ 以及 $q$ 个查询，每个查询由 $l, r$ 给出。对于每个查询，你需要求出 $f([a_l, a_{l+1}, \dots, a_r])$。

交互

你需要实现以下函数：

void init(int n, vector<long long> a)

• $n$ — 整数，表示数组长度；
• $a$ — 长度为 $n$ 的整数数组；
• 该函数不返回任何值。

long long ask(int l, int r)

• $l$ — 整数，表示查询的左边界；
• $r$ — 整数，表示查询的右边界；
• 该函数返回一个整数 — $f([a_l, a_{l+1}, \dots, a_r])$。

vector<long long> askAll(int q, vector<int> l, vector<int> r)

• $q$ — 整数，表示查询数量；
• $l$ — 长度为 $q$ 的整数数组；$l_i$ 表示第 $i$ 个查询的左边界；
• $r$ — 长度为 $q$ 的整数数组；$r_i$ 表示第 $i$ 个查询的右边界；
• 该函数返回一个整数数组；第 $i$ 个数必须等于第 $i$ 个查询的答案。

输入格式

第一行包含三个整数 $n, q, t$ ($1 \le n, q \le 2 \cdot 10^5$; $1 \le t \le 2$)，分别表示数字个数、查询数量以及查询格式。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i < 2^{60}$)，表示数组 $a$ 的元素。

接下来的 $q$ 行，每行包含两个整数 $l$ 和 $r$ ($1 \le l \le r \le n$)，表示第 $i$ 个查询的参数。

程序将首先调用 init 函数恰好一次。如果 $t = 1$，则会调用 askAll 函数恰好一次，包含所有查询。如果 $t = 2$，则 ask 函数将被调用恰好 $q$ 次。

输出格式

评测程序将在单独的行中输出 $q$ 个整数 — 查询的答案。

子任务

1. (3 分): $t = 1, a_i = a_1$ 对于 $1 \le i \le n$；
2. (8 分): $t = 1, a_i \neq a_j$ 对于 $i \neq j$；
3. (3 分): $t = 1, 2^m + n \le a_i < 2^{m+1}$ 对于某个自然数 $m$；
4. (9 分): $t = 1, a_i \le a_{i+1}$ 对于 $1 \le i < n$；
5. (10 分): $t = 1, n, q \le 1000$；
6. (11 分): $t = 1, l_i = 1$ 且 $r_i = i$ 对于 $1 \le i \le q$；
7. (10 分): $t = 1, n, q \le 50000$；
8. (25 分): $t = 1$；
9. (9 分): $t = 2, n, q \le 10^5$；
10. (12 分): $t = 2$。

样例

输入 1

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

输出 1

9
11
12
14
12
6

输入 2

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

输出 2

9
11
12
14
12
6