Description

There are many dandelions planted along a country path, and our problem is about these dandelions.

To simplify, we treat all the dandelions as a sequence of length $n$, $\{a_1,a_2..a_n\}$, where $a_i$ is a positive integer representing the type ID of the $i$-th dandelion.

For each query on an interval $[l, r]$, you need to report which type appears most frequently in the interval. If several types are tied, output the smallest type ID among them.

Note: your algorithm must be online.

Input Format

The first line contains two integers, representing the number of dandelions $n$ and the number of queries $m$.

The second line contains $n$ integers. The $i$-th integer is the type $a_i$ of the $i$-th dandelion.

Then follow $m$ lines. Each line contains two integers $l_0, r_0$, representing one query. The input is encrypted; the decryption is as follows:

Let the previous query’s result be $x$ (if this is the first query, then $x = 0$), and set $l=((l_0+x-1)\bmod n) + 1, r=((r_0+x-1) \bmod n) + 1$. If $l > r$, swap $l, r$.
The final query interval is the computed $[l, r]$.

Output Format

For each query, output one integer on its own line representing the answer.

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

1 
2 
1

Hint

Constraints

• For $20\%$ of the testdata, it is guaranteed that $n, m \le 3000$.
• For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 40000$, $1 \le m \le 50000$, $1 \le a_i \le 10^9$, $1 \leq l_0, r_0 \leq n$.

Translated by ChatGPT 5