Background

Dear Brother:

How are you doing in that city?

I’ve been very happy at home lately. Last night Grandma told me the story about that big villain called "Despair"! It ruined people’s houses and fields, and many children were killed by it, too. I think the bad guy who summoned such a scary monster is also very bad. But Grandma said he only did that when he was in great pain...

Recently, lots and lots of dandelions have grown all over the village. When the wind blows, these dandelions can float far, far away. I think if they could float into that city and let you see them, that would be wonderful!

Brother, please come back soon!

Love, your sister Violet

Azure smiled after reading this letter.

"Dandelions, huh..."

Problem 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