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

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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