Let \(v\) be a sequence of length \(K\). In one step, you can select an index \(i\) and change the value \(v_i\) to either \(v_i - 1\) or \(v_i + 1\). Let \(f(v_1, v_2, \dots, v_K)\) be the minimum number of steps required to satisfy \(v_1 \le v_2 \le \dots \le v_K\).

You are given an array \(s\) of length \(N\). You are required to answer \(Q\) independent queries of the type: For given pair \((l,r)\), what is the value of \(f(s_l, s_{l + 1}, \dots, s_r)\)?

Input format

First line: Two integers, \(N\) and \(Q\) \((1 \le N,Q \le 10^5)\)
Second line: \(N\) integers - \(s_1, s_2, \dots, s_N\) \((1 \le s_i \le 32)\)
Next \(Q\) lines: Two integers \(a_i\) and \(b_i\) \((1 \le a_i,b_i \le N)\). The \(i^{th}\) query will be equal to \((l_i,r_i) = (((a_i + last - 1) \mod \ N) + 1, ((b_i + last - 1) \mod N) + 1)\), where \(last\) is the answer for the last query. For the first query, consider \((l_1, r_1) = (a_1, b_1)\). The condition \(1 \le l_i \le r_i \le N\) is satisfied for all \(i\) with \(1 \le i \le Q\).

Output format

Print \(Q\) lines where the \(i^{th}\) line represents the answer for the \(i^{th}\) query.

Additional information

For \(20\) points: \(N,Q \le 512\) is satisfied

For additional \(30\) points: \(N \le 2^{16}, Q \le 2^{14}\) are satisfied

Original constraints for remaining points