어린 양은 피오르드 근처의 작은 어촌 마을에 살고 있으며, 연속된 $n$ 일 동안의 해수면 높이를 기록했습니다. $i$ 번째 날($1\leq i\leq n$)의 해수면 높이는 양의 정수 $h_i$ 입니다.

$l$ 번째 날부터 $r$ 번째 날까지 선택된 기간($l$ 과 $r$ 포함)에 대하여 다음과 같이 정의합니다:

• $M$ 은 이 기간 동안의 해수면 높이의 최댓값입니다;
• $A$ 는 $[l,r]$ 에서 해수면 높이가 처음으로 $M$ 에 도달한 날의 번호입니다;
• $B$ 는 $[l,r]$ 에서 해수면 높이가 마지막으로 $M$ 에 도달한 날의 번호입니다.

그러면 이 기간의 조석값은 $M\cdot(B-A)$ 로 정의됩니다. 만약 해수면 높이의 최댓값이 단 한 번만 나타난다면 $A=B$ 가 되며, 이때의 조석값은 $0$ 이 된다는 점에 유의하십시오.

어린 양은 온라인으로 $q$ 개의 질문을 합니다. 각 질문마다 $l$ 과 $r$ 이 주어지며, $[l,r]$ 내에서 부분 기간 $[x,y]$ (즉, $l\leq x\leq y\leq r$)를 선택하여 해당 기간의 조석값을 최대화해야 합니다.

입력

첫째 줄에 관측한 총 일수와 질의 횟수를 나타내는 두 정수 $n$ 과 $q$ ($1\leq n\leq 5\times 10^5$, $1\leq q\leq 3\times10^6$)가 주어집니다.

둘째 줄에 각 날의 해수면 높이를 순서대로 나타내는 $n$ 개의 양의 정수 $h_1, h_2, \dots, h_n$ ($1\leq h_i\leq 10^9$)이 주어집니다.

셋째 줄에 첫 번째 질의의 구간을 나타내는 두 정수 $l_1$ 과 $r_1$ ($1\leq l_1\leq r_1\leq n$)이 주어집니다.

$i$ 번째 질의($2\leq i\leq q$)에 대하여, $lastans$ 를 이전 질의의 답이라고 할 때 다음과 같이 정의합니다: $$ a_i = \left(l_{i-1} + lastans\cdot37\right) \bmod n + 1,\quad b_i = \left(l_{i-1} + r_{i-1} + lastans\cdot53\right) \bmod n + 1 $$

그러면 $i$ 번째 질의는 실제로 $l_i=\min(a_i,b_i)$, $r_i=\max(a_i,b_i)$ 가 됩니다.

출력

$ans_i$ 를 $i$ 번째 질의의 답이라고 할 때, 하나의 정수 $(ans_1+1) \oplus (ans_2+2) \oplus \cdots \oplus (ans_q+q)$ 를 출력하십시오.

$\oplus$ 는 비트 배타적 논리합(XOR) 연산을 나타냅니다.

예제

입력 1

8 5
5 8 2 8 4 9 3 9
2 7

출력 1

1

참고

첫 번째 질의의 구간은 $[2,7]$ 이며, 최적의 기간은 $[2,4]$ 이고 이때 해수면 높이의 최댓값은 $8$ 입니다. 기간 $[2,4]$ 에서 높이 $8$ 은 $2$ 번째 날에 처음 나타나고 $4$ 번째 날에 마지막으로 나타나므로, 해당 기간의 조석값은 $8\times(4-2)=16$ 입니다.

이후 생성되는 각 질의와 그 답은 순서대로 다음과 같습니다: $ [2,3]\to 0,\quad [3,6]\to 0,\quad [2,4]\to 16,\quad [3,7]\to 0. $

따라서 구하고자 하는 XOR 합은 $(16+1)\oplus (0+2)\oplus (0+3)\oplus (16+4)\oplus (0+5)=1$ 입니다.