题目描述

小 A 和小 B 在玩一个游戏：

现在有 $n$ 张卡牌，第 $i$ 张卡牌上写了 $a_i$，其中 $a_i \in [0,2^m-1]$。

游戏开始时两个人手上都没有卡牌，然后小 A 先手，两人轮流操作，每次取走一张卡牌。

• 小 A 的目的是最大化自己最后所有卡牌数字的按位异或和；
• 小 B 的目的是最小化小 A 最终手牌的按位异或和。

有 $q$ 次游戏，每次取出一个区间 $[l,r]$ 来进行游戏。你需要输出：该次游戏结束后，小 A 所有卡牌数字异或和中，最高位为 $0$ 的出现位置。

定义从低位到高位依次为第 $1$ 位到第 $m$ 位；如果不存在（即所有位都是 $1$），则输出 $0$。

输入格式

第一行三个数 $c,n,m$，$c$ 代表测试点编号。
第二行 $n$ 个数表示 $a_1,\ldots,a_n$。
第三行一个数 $q$ 表示询问次数。
接下来 $q$ 行，每行两个整数 $l,r$ 表示询问区间。

输出格式

输出 $q$ 行，第 $i$ 行输出第 $i$ 次询问的答案。

1 5 2
1 3 2 2 1
10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

0
1
0
2
0
2
0
1
0
1

样例解释

• $l=1,r=2$ 时，小 A 取 $3$ 即可，答案为 $3$。因为 $3$ 的每一位都是 $1$，所以输出 $0$。
• $l=1,r=3$ 时，小 A 先取 $1$，小 B 必取 $2$，小 A 再取 $3$，最终异或和为 $2$。因为 $2$ 的最低位为 $0$，故输出 $1$。

数据范围与提示

• 特殊性质 A：保证 $l=1$。
• 下发的第 $i$ 个大样例满足第 $i$ 种测试点限制；也可通过大样例的 $c$ 判断属于哪一类测试点。
• 对于所有数据：$0\le n,q\le 3\times 10^5$，$1\le m\le 20$，$0\le a_i\le 2^m-1$。