题目描述

小火车沉迷垃圾手游不能自拔，正在玩碧蓝航线，可惜小火车的舰（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 $ 行每行一个整数表示答案。

样例

input

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

output

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 $。