题目描述

风语镇外有一片很大的花田，田地里一共种着 $n$ 朵灵花，它们从左到右排成一列。第 $i$ 朵灵花有一个种类编号 $a_i$，编号是一个正整数。

镇上的记录员每天都会查看某一段连续花田。他一共会提出 $m$ 次询问，每次给出一段区间 $[l,r]$，你需要回答这段区间中出现次数最多的灵花种类。

如果有多个种类在区间中出现次数相同，并且都达到了最多次数，那么输出种类编号最小的那一个。

需要注意的是，记录员为了防止别人提前知道询问内容，对输入的询问进行了加密。因此，你的程序必须按照顺序在线处理每一次询问。

设上一次询问的答案为 $x$。如果当前是第一次询问，则 $x=0$。输入中给出的两个数为 $l_0,r_0$，真实询问区间按照下面的方式计算：

$l=((l_0+x-1)\bmod n)+1$

$r=((r_0+x-1)\bmod n)+1$

如果 $l>r$，则交换 $l,r$。

最终需要回答的就是区间 $[l,r]$ 中出现次数最多、若次数相同则种类编号最小的灵花编号。

输入格式

第 $1$ 行包含两个整数 $n,m$，分别表示灵花数量和询问次数。

第 $2$ 行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，其中 $a_i$ 表示第 $i$ 朵灵花的种类编号。

接下来 $m$ 行，每行包含两个整数 $l_0,r_0$，表示一次经过加密的询问。

输出格式

对于每次询问，输出一行一个整数，表示该次询问的答案。

样例

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

1
2
1

样例说明

数据范围

• 对于 $20$ 的数据，保证 $n,m \leq 3000$。
• 对于 $100$ 的数据，保证 $1 \leq n \leq 40000$，$1 \leq m \leq 50000$，$1 \leq a_i \leq 10^9$，$1 \leq l_0,r_0 \leq n$。