ศาสตราจารย์จอย ผู้เป็นผู้เชี่ยวชาญชั้นนำด้านประวัติศาสตร์ของประเทศ IOI ได้รับสมุดบันทึกที่เชื่อว่าเขียนโดยชาวประเทศ IOI ในสมัยโบราณ เพื่อศึกษาชีวิตในประเทศ IOI สมัยโบราณจากสมุดบันทึกนี้ ศาสตราจารย์จอยจึงตัดสินใจตรวจสอบเหตุการณ์ที่บันทึกไว้

สมุดบันทึกนี้บันทึกเหตุการณ์ตลอด $N$ วัน โดยมีวันละหนึ่งเหตุการณ์ เหตุการณ์ถูกแบ่งออกเป็นหลายประเภท ประเภทของเหตุการณ์ในวันที่ $i$ ($1\le i\le N$) แทนด้วยจำนวนเต็ม $X_i$ ยิ่งค่า $X_i$ มาก ก็ถือว่าเป็นเหตุการณ์ที่มีขนาดใหญ่ขึ้น

ศาสตราจารย์จอยตัดสินใจวิเคราะห์สมุดบันทึกด้วยวิธีต่อไปนี้

1. เลือกช่วงวันที่ต่อเนื่องกันช่วงหนึ่งจาก $N$ วันในสมุดบันทึกเป็นช่วงเวลาที่จะวิเคราะห์
2. กำหนดความสำคัญของประเภทเหตุการณ์ $t$ เป็น $t\times(\text{จำนวนเหตุการณ์ประเภท }t\text{ ในช่วงเวลานั้น})$
3. คำนวณความสำคัญของประเภทเหตุการณ์ทุกประเภท แล้วหาค่ามากที่สุด

ศาสตราจารย์จอยมอบหมายให้คุณสร้างโปรแกรมสำหรับการวิเคราะห์ โดยต้องการให้โปรแกรมหาความสำคัญมากที่สุดได้เมื่อได้รับช่วงเวลาที่จะวิเคราะห์

งานที่ต้องทำ

เมื่อได้รับประเภทของเหตุการณ์ตลอด $N$ วันในสมุดบันทึก และคำถาม $Q$ ข้อที่ระบุช่วงเวลาในสมุดบันทึก จงเขียนโปรแกรมหาความสำคัญมากที่สุดของเหตุการณ์สำหรับคำถามแต่ละข้อ

ข้อมูลนำเข้า

อ่านข้อมูลต่อไปนี้จากข้อมูลนำเข้ามาตรฐาน

• บรรทัดแรกมีจำนวนเต็ม $N,Q$ คั่นด้วยช่องว่าง หมายความว่าสมุดบันทึกมีข้อมูล $N$ วัน และมีคำถาม $Q$ ข้อ
• บรรทัดถัดไปมีจำนวนเต็ม $N$ จำนวน $X_1,\ldots,X_N$ คั่นด้วยช่องว่าง โดย $X_i$ ($1\le i\le N$) ระบุประเภทของเหตุการณ์ในวันที่ $i$
• บรรทัดที่ $j$ ($1\le j\le Q$) จาก $Q$ บรรทัดถัดไปมีจำนวนเต็ม $A_j,B_j$ ($1\le A_j\le B_j\le N$) คั่นด้วยช่องว่าง หมายความว่าคำถามข้อที่ $j$ เกี่ยวกับช่วงเวลาตั้งแต่วันที่ $A_j$ ถึงวันที่ $B_j$

ข้อมูลส่งออก

แสดงผล $Q$ บรรทัดทางข้อมูลส่งออกมาตรฐาน ในบรรทัดที่ $j$ ($1\le j\le Q$) ให้แสดงจำนวนเต็มที่ระบุความสำคัญมากที่สุดสำหรับคำถามข้อที่ $j$

ข้อจำกัด

ข้อมูลนำเข้าทั้งหมดเป็นไปตามเงื่อนไขต่อไปนี้

• $1\le N\le100\,000$
• $1\le Q\le100\,000$
• $1\le X_i\le1\,000\,000\,000$ ($1\le i\le N$)

งานย่อย

งานย่อย 1 [5 คะแนน]

เป็นไปตามเงื่อนไขต่อไปนี้

• $N\le100$
• $Q\le100$

งานย่อย 2 [10 คะแนน]

เป็นไปตามเงื่อนไขต่อไปนี้

• $N\le5\,000$
• $Q\le5\,000$

งานย่อย 3 [25 คะแนน]

• ไม่มี $i,j$ ($1\le i\le Q$, $1\le j\le Q$, $i\ne j$) ที่ทำให้ $A_i\le A_j\le B_j\le B_i$

งานย่อย 4 [60 คะแนน]

ไม่มีข้อจำกัดเพิ่มเติม

ตัวอย่าง

ข้อมูลนำเข้า 1

5 5
9 8 7 8 9
1 2
3 4
4 4
1 4
2 4

ข้อมูลส่งออก 1

9
8
8
16
16

หมายเหตุ

• สมุดบันทึกนี้มีข้อมูล 5 วัน และประเภทของเหตุการณ์ที่บันทึกไว้คือ $7$, $8$ หรือ $9$
• ตั้งแต่วันที่ 1 ถึงวันที่ 2 ความสำคัญของประเภทเหตุการณ์ $7$ คือ $7\times0=0$ ของประเภท $8$ คือ $8\times1=8$ และของประเภท $9$ คือ $9\times1=9$ ดังนั้นค่าสูงสุดคือ $9$
• ตั้งแต่วันที่ 3 ถึงวันที่ 4 ความสำคัญของประเภทเหตุการณ์ $7$ คือ $7\times1=7$ ของประเภท $8$ คือ $8\times1=8$ และของประเภท $9$ คือ $9\times0=0$ ดังนั้นค่าสูงสุดคือ $8$
• ในวันที่ 4 ความสำคัญของประเภทเหตุการณ์ $7$ คือ $7\times0=0$ ของประเภท $8$ คือ $8\times1=8$ และของประเภท $9$ คือ $9\times0=0$ ดังนั้นค่าสูงสุดคือ $8$
• ตั้งแต่วันที่ 1 ถึงวันที่ 4 ความสำคัญของประเภทเหตุการณ์ $7$ คือ $7\times1=7$ ของประเภท $8$ คือ $8\times2=16$ และของประเภท $9$ คือ $9\times1=9$ ดังนั้นค่าสูงสุดคือ $16$
• ตั้งแต่วันที่ 2 ถึงวันที่ 4 ความสำคัญของประเภทเหตุการณ์ $7$ คือ $7\times1=7$ ของประเภท $8$ คือ $8\times2=16$ และของประเภท $9$ คือ $9\times0=0$ ดังนั้นค่าสูงสุดคือ $16$

ข้อมูลนำเข้า 2

8 4
9 9 19 9 9 15 9 19
1 4
4 6
3 5
5 8

ข้อมูลส่งออก 2

27
18
19
19

หมายเหตุ

ข้อมูลนำเข้านี้เป็นไปตามข้อจำกัดของงานย่อย 3

ข้อมูลนำเข้า 3

12 15
15 9 3 15 9 3 3 8 16 9 3 17
2 7
2 5
2 2
1 12
4 12
3 6
11 12
1 7
2 6
3 5
3 10
7 10
1 4
4 8
4 8

ข้อมูลส่งออก 3

18
18
9
30
18
15
17
30
18
15
18
16
30
15
15