Domba Kecil tinggal di sebuah desa nelayan kecil di tepi fyord. Ia mencatat ketinggian permukaan laut selama $n$ hari berturut-turut; pada hari ke-$i$ ($1\leq i\leq n$), ketinggian permukaan laut adalah bilangan bulat positif $h_i$.
Untuk suatu periode terpilih dari hari ke-$l$ hingga hari ke-$r$ (termasuk $l$ dan $r$), misalkan:
- $M$ adalah nilai maksimum ketinggian permukaan laut selama periode ini;
- $A$ adalah nomor hari pertama dalam $[l,r]$ ketika ketinggian permukaan laut mencapai $M$;
- $B$ adalah nomor hari terakhir dalam $[l,r]$ ketika ketinggian permukaan laut mencapai $M$.
Maka nilai pasang surut dari periode ini didefinisikan sebagai $M\cdot(B-A)$. Perhatikan bahwa jika nilai maksimum ketinggian permukaan laut hanya muncul satu kali, maka $A=B$, dan nilai pasang surut saat itu adalah $0$.
Domba Kecil akan mengajukan $q$ pertanyaan secara daring (online). Setiap pertanyaan memberikan $l$ dan $r$, dan meminta Anda memilih sub-periode $[x,y]$ di dalam $[l,r]$ (yaitu $l\leq x\leq y\leq r$) sehingga nilai pasang surut dari sub-periode tersebut maksimum.
Masukan
Baris pertama berisi dua bilangan bulat $n$ dan $q$ ($1\leq n\leq 5\times 10^5$, $1\leq q\leq 3\times10^6$), masing-masing menyatakan total hari pengamatan dan jumlah kueri.
Baris kedua berisi $n$ bilangan bulat positif $h_1, h_2, \dots, h_n$ ($1\leq h_i\leq 10^9$), secara berurutan menyatakan ketinggian permukaan laut pada setiap hari.
Baris ketiga berisi dua bilangan bulat $l_1$ dan $r_1$ ($1\leq l_1\leq r_1\leq n$), menyatakan interval kueri pertama.
Untuk kueri ke-$i$ ($2\leq i\leq q$), misalkan $lastans$ adalah jawaban dari kueri sebelumnya, tetapkan: $$ 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 $$
Maka kueri ke-$i$ sebenarnya adalah $l_i=\min(a_i,b_i)$ dan $r_i=\max(a_i,b_i)$.
Keluaran
Misalkan $ans_i$ menyatakan jawaban untuk kueri ke-$i$. Keluarkan satu bilangan bulat: $(ans_1+1) \oplus (ans_2+2) \oplus \cdots \oplus (ans_q+q)$.
Perhatikan bahwa $\oplus$ menyatakan operasi bitwise XOR.
Contoh
Masukan 1
8 5 5 8 2 8 4 9 3 9 2 7
Keluaran 1
1
Catatan
Interval untuk kueri pertama adalah $[2,7]$, dan periode optimalnya adalah $[2,4]$, di mana ketinggian permukaan laut maksimumnya adalah $8$. Dalam periode $[2,4]$, ketinggian $8$ pertama kali muncul pada hari ke-$2$ dan terakhir kali muncul pada hari ke-$4$, sehingga nilai pasang surut periode ini adalah $8\times(4-2)=16$.
Kueri-kueri berikutnya yang dibangkitkan beserta jawabannya secara berurutan adalah: $ [2,3]\to 0,\quad [3,6]\to 0,\quad [2,4]\to 16,\quad [3,7]\to 0. $
Oleh karena itu, nilai XOR sum yang diminta adalah $(16+1)\oplus (0+2)\oplus (0+3)\oplus (16+4)\oplus (0+5)=1$.