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