题目描述

本题采用交互式评测方式，目前仅支持 C++ 语言提交。

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

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

按位异或 运算（$\oplus$）的定义：对于非负整数 $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},\ldots,a_r])$。

你需要实现以下函数：

void init(integer n, array of integers a)

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

integer ask(integer l, integer r)

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

array of integers askAll(integer q, array of integers l, array of integers r)

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

这三个函数在 C++ 语言中可以视作：

void init(int n, const vector<long long> &a);
long long ask(int l, int r);
vector<long long> askAll(int q, const vector<int> &l, const vector<int> &r);

输入格式

第一行包含三个整数 $n$、$q$ 和 $t$（$1 \leq n, q \leq 2 \cdot 10^5$；$1 \leq t \leq 2$）—— 分别表示数字数量、查询数量和查询格式。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i < 2^{60}$）—— 数组 $a$ 的元素。

接下来 $q$ 行每行包含两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq n$）—— 第 $i$ 个查询的参数。

函数 $\tt{init}$ 将被调用恰好一次。

如果 $t=1$，则函数 $\tt{askAll}$ 将被调用恰好一次来处理所有查询。如果 $t=2$，则函数 $\tt{ask}$ 将被调用恰好 $q$ 次。

输出格式

评测程序将输出 $q$ 个整数，每个查询的答案各占一行。

输入输出样例 #1

输入 #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

输入 #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

说明/提示

评分标准

• （$3$ 分）：$t=1$，且对所有 $1\le i\le n$ 有 $a_i=a_1$；
• （$8$ 分）：$t=1$，且对所有 $i \neq j$ 有 $a_i \neq a_j$；
• （$3$ 分）：$t=1$，且存在自然数 $m$ 使得对所有 $i$ 有 $2^m+n \le a_i<2^{m+1}$；
• （$9$ 分）：$t=1$，且对所有 $1 \le i < n$ 有 $a_i \le a_{i+1}$；
• （$10$ 分）：$t=1$，且 $n, q \le 1000$；
• （$11$ 分）：$t=1$，且对所有 $1\le i\le q$ 有 $l_i=1$ 且 $r_i=i$；
• （$10$ 分）：$t=1$，且 $n, q \le 50000$；
• （$25$ 分）：$t=1$；
• （$9$ 分）：$t=2$，且 $n, q \le 10^5$；
• （$12$ 分）：$t=2$。