题目描述
小火车沉迷垃圾手游不能自拔，正在玩碧蓝航线，可惜小火车的舰（lao）队（po）练度太低打不过副本，所以他只好去刷其余的副本来升级。总共有n个副本编号从1到n，每个副本有个难度值ai，小火车每天按照顺序刷连续的一段副本，第j天会刷的副本必须落在l到r之间。但是他是个很懒的人，每天一开始他的懒惰值为0，当他刷完一个副本以后懒惰值就会异或上ai，小火车希望懒惰值一直保持单调不下降，请问每天他都有多少种刷副本的方法？

输入格式

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

输出格式

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

样例

样例输入

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

样例输出

4
6
4

数据范围

对于20的数据 n,m≤5000数据随机；
对于另外20% 的数据 m=1,l=0,r=n−1
对于另外30%的数据随机；
对于100%的数据 n,m≤100000,0≤ai≤10^9。

来源

「2017 山东二轮集训 Day1」