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

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

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

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

珂朵莉：所以，现在的我，不管别人怎么说，一定是这个世界上最幸福的女孩！

珂朵莉给了仓鼠n个事件，其中第i个事件的类型是a _i。每次，珂朵莉会选择一段区间[l,r]，询问该区间的事件中，重要程度的最大值。
区间[l,r]中事件的重要程度定义如下：对于类型为k的事件，重要程度为

当条件X成立时，[X]的值为1，否则为0。也就是说，这个重要程度等价于k乘上a _l~a _r中k出现的次数。
为了考验仓鼠，珂朵莉给出的区间是加密的，每次回答询问前需要先进行解密。对于加密后的区间l ₀,r ₀，真实的区间[l, r]为：


l=(l ₀xor lastans) mod n+ 1
r=(r ₀xor lastans) mod n+ 1
其中xor表示按位异或，mod表示取模运算。注意解密后的l,r可能不满足l≤r，此时你应该交换它们的值，再回答询问。

第一行两个整数n,m，表示一共有n个事件，m次询问。

第二行有n个整数a₁~a_n

接下来m行，每行两个整数l₀,r₀，表示加密过的询问区间。

对于所有的数据，1≤n,m≤100000, 0≤a_i,l₀,r₀≤10⁹。

输出 m行，每行一个数，表示询问区间的事件中，重要程度的最大值。

5次询问的区间分别是[1, 2], [3, 4], [2, 2], [2, 4], [1, 4].

武汉大学2020年新生程序设计大赛