题目描述
珂朵莉：我曾经发誓，要永远和他在一起，可以如此发誓，让我无比幸福。
威廉：我曾经发誓，要一直和她在一起，可以这样发誓，让我无比平静。
珂朵莉：我曾经觉得，自己非常喜欢这个人，可以有这样的感受，让我无比幸福。
威廉：我曾经觉得，自己非常珍视这个人，可以有这样的感受，让我无比喜悦。
珂朵莉：他曾经对我说：“我一定会让你幸福”，能听到他那样说，让我很幸福。
威廉：我曾经对她说：我一定会让你幸福”，能对她那样说，让我很满足。
珂朵莉：他将他的幸福，分了这么多给我
威廉：她将她的东西，送了这么多给我，可我却……
珂朵莉：所以，现在的我，不管别人怎么说，一定是这个世界上最幸福的女孩！
珂朵莉给了仓鼠n个事件，其中第i个事件的类型是ai。每次，珂朵莉会选择一段区间[l,r]，询问该区间的事件中，重要程度的最大值。
区间[l,r]中事件的重要程度定义如下：对于类型为k的事件，重要程度为
当条件X成立时，[X]的值为1，否则为0。也就是说，这个重要程度等价于k乘上al~ar中k出现的次数。
为了考验仓鼠，珂朵莉给出的区间是加密的，每次回答询问前需要先进行解密。对于加密后的区间l0 ,r0，真实的区间[l, r]为：
l=(l0 xor lastans) mod n+ 1
r=(r0 xor lastans) mod n+ 1
其中xor表示按位异或，mod表示取模运算。注意解密后的l,r可能不满足l≤r，此时你应该交换它们的值，再回答询问。
输入
第一行两个整数n,m，表示一共有n个事件，m次询问。
第二行有n个整数a1~an
接下来m行，每行两个整数l0, r0，表示加密过的询问区间。
对于所有的数据，1≤n, m ≤100000, 0≤ai, l0,r0≤109。
输出
输出m行，每行一个数，表示询问区间的事件中，重要程度的最大值。
样例输入
Copy
5 5
9 8 7 8 9
0 1
10 11
9 9
11 9
16 19
样例输出 Copy
9
8
8
16
16
提示
5次询问的区间分别是[1, 2], [3, 4], [2, 2], [2, 4], [1, 4].
来源/分类