Migrated from Lutece 2759 经典题

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

这是一道经典题。

你有一个长度为 $n$ 的序列 $S$ , 每次询问一个区间 $l,r$ ，你需要找到区间内最大的只出现一次的数。

为了保证做法的在线性，本题采用了特殊方式的读入。 假设你维护了一个变量 $lastans$，初始值为 $0$ 。 对于每个读入的区间 $[l, r]$，设

$$x = ((l + lastans) \bmod n) + 1\\ y = ((r + lastans) \bmod n) + 1 $$

则实际上询问的区间为 $[\min(x,y),\max(x,y)]$。

Input

第一行输入两个正整数 $n,m$，分别表示序列长度和询问次数。 第二行输入 $n$ 个非负整数 $S_1, S_2, \cdots, S_n$，即序列 $S$。 第 $3$ 至第 $m+2$ 行，每行输入 $l,r$，表示一次询问。

Output

输出 $m$ 行，每行一个整数，表示对应询问的答案。

Samples

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

6
6
3
5

Constraints

$1\le n \le 100000$，$1\le m \le 200000$ $1\le l,r,S_i \le n$

Resources

2022 UESTC ICPC Training for Data Structures