You have a sequence a of length n and you want to answer q queries determined by 2 integers l and r. You take all numbers present in subsequence $(a_l, a_{l + 1}, \dots , a_r)$, let them be $b_1, b_2, \dots , b_t$ and number of occurrenses of each number in this subsequence be $c_1, c_2, \dots, c_t$ respectively. The answer for per query is equal to $\min |c_i - c_j|$ for $1 \le i < j \le t$ or 1 if $t = 1$.

$\textbf{Input}$

The first line contains 2 integers - n and q $(1 \le n , q \le 100 \; 000)$.

The second line contains n numbers - $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^9)$.

Each of the next q lines contains 2 integers - $u_i,v_i$ $(1 \le u_i, v_i \le n)$.

You will need to answer the queries online so the information is encoded, if the answer for $(i - 1) ^ {th}$ query is $last$ (initially $last = 0$) then the $i^{th}$ query is :

$l_i = ((u_i + last) \; mod \; n) + 1$

$r_i = ((v_i + last) \; mod \; n) + 1$

Note that "last" can be -1 in some cases.

$\textbf{Output}$

Output q lines, the $i^{th}$ line contains the answer for the $i^{th}$ query.