Cừu Nhỏ sống ở một làng chài nhỏ bên vịnh hẹp. Cậu đã ghi lại độ cao mực nước biển trong $n$ ngày liên tiếp; vào ngày thứ $i$ ($1\leq i\leq n$), độ cao mực nước biển là một số nguyên dương $h_i$.

Đối với một khoảng thời gian được chọn từ ngày thứ $l$ đến ngày thứ $r$ (bao gồm cả $l$ và $r$), đặt:

• $M$ là giá trị lớn nhất của độ cao mực nước biển trong khoảng thời gian này;
• $A$ là chỉ số của ngày đầu tiên trong $[l,r]$ mà độ cao mực nước biển đạt tới $M$;
• $B$ là chỉ số của ngày cuối cùng trong $[l,r]$ mà độ cao mực nước biển đạt tới $M$.

Khi đó, giá trị thủy triều của khoảng thời gian này được định nghĩa là $M\cdot(B-A)$. Lưu ý rằng nếu giá trị lớn nhất của độ cao mực nước biển chỉ xuất hiện một lần thì $A=B$, và giá trị thủy triều khi đó bằng $0$.

Cừu Nhỏ sẽ đặt $q$ câu hỏi trực tuyến (online). Mỗi câu hỏi sẽ cho $l$ và $r$, yêu cầu bạn chọn một khoảng thời gian con $[x,y]$ trong $[l,r]$ (tức là $l\leq x\leq y\leq r$) sao cho giá trị thủy triều của khoảng thời gian đó là lớn nhất.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $q$ ($1\leq n\leq 5\times 10^5$, $1\leq q\leq 3\times10^6$), lần lượt biểu thị tổng số ngày quan sát và số lượng truy vấn.

Dòng thứ hai chứa $n$ số nguyên dương $h_1, h_2, \dots, h_n$ ($1\leq h_i\leq 10^9$), lần lượt biểu thị độ cao mực nước biển của từng ngày.

Dòng thứ ba chứa hai số nguyên $l_1$ và $r_1$ ($1\leq l_1\leq r_1\leq n$), biểu thị đoạn của truy vấn đầu tiên.

Đối với truy vấn thứ $i$ ($2\leq i\leq q$), giả sử $lastans$ là đáp án của truy vấn trước đó, đặt: $$ 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 $$

Khi đó truy vấn thứ $i$ thực tế là $l_i=\min(a_i,b_i)$, $r_i=\max(a_i,b_i)$.

Dữ liệu ra

Gọi $ans_i$ là đáp án của truy vấn thứ $i$, hãy in ra một số nguyên: $(ans_1+1) \oplus (ans_2+2) \oplus \cdots \oplus (ans_q+q)$.

Lưu ý rằng $\oplus$ biểu thị phép toán XOR bit.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1

Ghi chú

Đoạn của truy vấn đầu tiên là $[2,7]$, khoảng thời gian tối ưu là $[2,4]$, trong đó độ cao mực nước biển lớn nhất là $8$. Trong khoảng thời gian $[2,4]$, độ cao $8$ xuất hiện lần đầu vào ngày thứ $2$ và xuất hiện lần cuối vào ngày thứ $4$, vì vậy giá trị thủy triều của khoảng thời gian này là $8\times(4-2)=16$.

Các truy vấn được sinh ra tiếp theo và đáp án tương ứng lần lượt là: $ [2,3]\to 0,\quad [3,6]\to 0,\quad [2,4]\to 16,\quad [3,7]\to 0. $

Do đó tổng XOR cần tìm là $(16+1)\oplus (0+2)\oplus (0+3)\oplus (16+4)\oplus (0+5)=1$.