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.