「2017 山东二轮集训 Day1」第一题

传统 1000 ms 512 MiB

$153$ 通过 $380$ 提交

题目描述

小火车沉迷垃圾手游不能自拔，正在玩碧蓝航线，可惜小火车的舰（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,\quad 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$。