题目描述

在乡下的小路旁种着许多蒲公英，而我们的问题正是与这些蒲公英有关。

为了简化起见，我们把所有的蒲公英看成一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$，其中 $a_i$ 为一个正整数，表示第 $i$ 棵蒲公英的种类编号。

而每次询问一个区间 $[l,r]$，你需要回答区间里出现次数最多的是哪种蒲公英，如果有若干种蒲公英出现次数相同，则输出种类编号最小的那个。

输入格式

第一行两个整数 $n, m$，表示有 $n$ 株蒲公英，$m$ 次询问。

接下来一行 $n$ 个空格隔开的整数 $a_i$，表示蒲公英的种类。

再接下来 $m$ 行每行两个整数 $l_0, r_0$，我们令上次询问的结果为 $x$（如果这是第一次询问，则 $x=0$）。

令 $l = ((l_0 + x - 1) \bmod n) + 1,\; r = ((r_0 + x - 1) \bmod n) + 1$，如果 $l > r$，则交换 $l, r$。

最终的询问区间为 $[l, r]$。

输出格式

输出 $m$ 行。

每行一个整数，表示每次询问的结果。

样例

输入样例：

6 3 
1 2 3 2 1 2 
1 5 
3 6 
1 5

输出样例：

1 
2 
1

样例解释

$n=6, m=3$

序列：$[1,2,3,2,1,2]$

1. 第一次询问，$x=0$，$l_0=1, r_0=5$
   $l = ((1+0-1)\bmod 6)+1 = 1$
   $r = ((5+0-1)\bmod 6)+1 = 5$
   区间 $[1,5]$：元素为 $[1,2,3,2,1]$，出现次数：1出现2次，2出现2次，3出现1次。最多出现2次，编号最小的是1，输出 $1$，$x$ 更新为1。

2. 第二次询问，$l_0=3, r_0=6$，上次结果 $x=1$
   $l = ((3+1-1)\bmod 6)+1 = 4$
   $r = ((6+1-1)\bmod 6)+1 = 6$
   区间 $[4,6]$：元素为 $[2,1,2]$，出现次数：2出现2次，1出现1次，输出 $2$，$x$ 更新为2。

3. 第三次询问，$l_0=1, r_0=5$，上次结果 $x=2$
   $l = ((1+2-1)\bmod 6)+1 = 3$
   $r = ((5+2-1)\bmod 6)+1 = 1 \Rightarrow l>r$，交换 $l=1, r=3$
   区间 $[1,3]$：元素为 $[1,2,3]$，出现次数均为1次，编号最小的是1，输出 $1$。

数据范围

• $1 \le n \le 40000$
• $1 \le m \le 50000$
• $1 \le a_i \le 10^9$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB