Барашек живёт в маленькой рыбацкой деревне на берегу фьорда. Он записывал высоту уровня моря на протяжении $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$, а вам нужно выбрать подпромежуток $[x,y]$ внутри $[l,r]$ (то есть $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$.