题目描述

给出一个长度为 $n$ 的序列，给出 $m$ 个询问：在 $[l,r]$ 之间找到一个在这个区间里 只出现过一次的数，并且要求找的这个数尽可能大。如果找不到这样的数，则直接输出 $0$。强制在线。

输入格式

输入第一行为两个整数 $n, m$. $n$ 是序列长度, $m$ 是询问数.

第二行为 $n$ 个整数, 描述这个序列 $\{ a_i\}$.

接下来 $m$ 行, 每行两个整数 $x, y$. 询问区间 $[l,r]$ 由下列规则产生:

$l=min((x+lastans)mod \ n+1,(y+lastans) mod \ n+1)$

$r=max((x+lastans)mod \ n+1,(y+lastans) mod \ n+1)$

$lastans$ 表示上一个询问的答案，一开始 $lastans$ 为 $0$.

输出格式

一共 $m$ 行，每行给出每个询问的答案。

样例输入

10 10
6 4 9 10 9 10 9 4 10 4
3 8
10 1
3 4
9 4
8 1
7 8
2 9
1 1
7 3
9 9

样例输出

4
10
10
0
0
10
0
4
0
4

数据范围

时间限制应调整为共 40s, 空间限制 600 MB

$n \leq 10^5, m \leq 2 \times 10^5$