Баранчик живе в маленькому рибальському селі на березі фіорду. Він записував висоту рівня моря протягом $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$.