题目描述

小火车沉迷垃圾手游不能自拔，正在玩碧蓝航线，可惜小火车的舰（lao）队（po）练度太低打不过副本，所以他只好去刷其余的副本来升级。

总共有 $n$ 个副本编号从 $1$ 到 $n$，每个副本有个难度值 $a_i$，小火车每天按照顺序刷连续的一段副本，第 $j$ 天会刷的副本必须落在 $l$ 到 $r$ 之间。但是他是个很懒的人，每天一开始他的懒惰值为 $0$，当他刷完一个副本以后懒惰值就会异或上 $a_i$，小火车希望懒惰值一直保持单调不下降，请问每天他都有多少种刷副本的方法？

输入格式

第一行一个整数 $n$，表示副本数量。
接下来一行 $n$ 个整数表示副本的难度。
接下来一行一个整数 $m$ 表示天数。
接下来 $m$ 行每行两个整数 $a, b$ 表示一组询问，为了体现程序的在线性，题目中说的 $l$ 和 $r$ 都需要计算得到，设上个询问的答案为 $\text{lastAns}$（初始为 $0$），则 $l = (( a + \text{lastAns}) \bmod n) + 1, r = ((b + \text{lastAns}) \bmod n) + 1$，当然如果这样求得的 $l$ 和 $r$ 满足 $l > r$ 请将 $l$ 和 $r$ 交换。

输出格式

$m$ 行每行一个整数表示答案。

样例

4
1 2 3 4
3
1 3
0 3
3 1

4
6
4

数据范围与提示

对于 $20\$ 的数据 $n, m \leq 5000$，数据随机；
对于另外 $20\%$ 的数据 $m = 1, l = 0, r = n - 1$；
对于另外 $30\%$ 的数据随机；
对于 $100\%$ 的数据 $n, m \leq 100000, 0 \leq a_i \leq 10 ^ 9$。