Қошақан фьорд жағасындағы шағын балықшылар ауылында тұрады. Ол қатарынан $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$ тең.