ลูกแกะอาศัยอยู่ในหมู่บ้านชาวประมงเล็กๆ ริมฟยอร์ด เขาได้บันทึกความสูงของระดับน้ำทะเลติดต่อกันเป็นเวลา $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 ระดับบิต (bitwise 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$