问题2706--仓鼠与珂朵莉

2706: 仓鼠与珂朵莉

时间限制: 3 Sec  内存限制: 512 MB
提交: 5  解决: 2
[状态] [讨论版] [提交] [命题人:]
题目描述

珂朵莉:我曾经发誓,要永远和他在一起,可以如此发誓,让我无比幸福。
威廉:我曾经发誓,要一直和她在一起,可以这样发誓,让我无比平静。

珂朵莉:我曾经觉得,自己非常喜欢这个人,可以有这样的感受,让我无比幸福。
威廉:我曾经觉得,自己非常珍视这个人,可以有这样的感受,让我无比喜悦。

珂朵莉:他曾经对我说:“我一定会让你幸福”,能听到他那样说,让我很幸福。
威廉:我曾经对她说:我一定会让你幸福”,能对她那样说,让我很满足。

珂朵莉:他将他的幸福,分了这么多给我
威廉:她将她的东西,送了这么多给我,可我却……

珂朵莉:所以,现在的我,不管别人怎么说,一定是这个世界上最幸福的女孩!
 
珂朵莉给了仓鼠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,表示加密过的询问区间。

对于所有的数据,1n, m 100000, 0ai, l0,r0109

输出
输出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].