题目背景

诶……你以为今天有两道非传统吗……只是骗骗你的啦！

即使是面对自己最喜欢的人，美好的回忆也会在时间的流逝中慢慢褪色。Bella 时常感叹「忘却」这一人类自我保护的本能，有时也会带来许多痛苦。作为队长，她对每一位女孩都了如指掌。她也知道她们的苦衷，但往日那欣欣向荣的场景最终仍是镜花水月。

幸好，心思细腻的少女慢慢学会了用信息的载体记录下几个女孩子之间最美好的瞬间。她明白遗忘并不是她的错：只要能看到那些文字，过去的回忆便历历在目。

题目描述

对于一段长度为 $m$ 的目标记忆序列，Bella 会用以下方法来重拾记忆。

• 记目标记忆序列为 $b$，当前记忆序列为 $c$，$c$ 的初值全为 $0$。
• Bella 的思绪可以视为整数 $x$，初始为 $0$。
• Bella 可以消耗 $1$ 秒阅读日记，将 $x$ 增大 $1$。
• Bella 可以消耗 $1$ 秒回忆一个瞬间，选择一个 $i$，然后将 $c_i$ 异或上 $x$。

我们记拾回一段记忆序列的最小时间 $F(b)$ 为使得 $c=b$ 需要的最小秒数。

Bella 有一段长度为 $n$ 的记忆序列 $a$。她会向你询问 $q$ 次遗忘，每次给出两个整数 $l,r$，你需要求出拾回子区间 $a[l,r]$ 对应记忆需要的最小时间，即 $F(a[l,r])$。

有时，少女会向你写信来询问，你只需要一次性回答她的所有问题即可；另一些时候，少女则会直接当面询问你，此时你需要在她提出每个问题后立刻回答。

交互格式

你需要实现三个函数。

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

每次调用会给出一个整数 $n$ 和长度为 $n$ 的序列 $a$，代表记忆的内容。在每一组数据中，这个函数会在下文函数调用前调用一次。

long long ask(int l, int r);

每次调用会给出两个整数 $l,r$，你需要返回 $F(a[l,r])$。在一组需要在线回答的数据中，这个函数会被调用 $q$ 次。

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

每次调用会给出两个数组 $l,r$，你需要返回一个数组 $z$，使得 $z_i=F(a[l_i,r_i])$。在一组不需要在线回答的数据中，这个函数会被调用一次。

输入格式

以下部分为 grader 的输入格式，你不应该在程序中读入任何内容。

第一行输入三个整数 $n,q,t$，代表序列长度、询问个数和在线参数。

第二行输入 $n$ 个整数 $a_i$。

接下来 $q$ 行，每行输入两个整数 $l_i,r_i$。

如果 $t=1$，代表这组数据不需要在线回答；否则代表需要在线回答。

输出格式

以下部分为 grader 的输出格式，你不应该在程序中输出任何内容。

$q$ 行，每行一个整数，代表对应询问的答案。

样例 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

数据范围

本题共 10 个测试点，你需要通过一个测试点的全部测试数据才能获得该测试点的分数。

对于所有数据，$1\le n,q\le 2\times 10^5$，$t\in\{1,2\}$，$1\le a_i<2^{60}$，$1\le l\le r\le n$。

请注意下发 grader 和实际评测的 grader 的实现可能不同。