ในพิธีเปิด IOI 2018 ผู้เข้าแข่งขัน $N$ คนเดินขบวนเป็นแถว ซึ่งแทนด้วยเส้นจำนวน ผู้เข้าแข่งขันทุกคนหันไปทางทิศบวกของเส้นจำนวน ณ เวลา $0$ ผู้เข้าแข่งขันคนที่ $i$ ($1 \le i \le N$ นับจากด้านหน้า) อยู่ที่พิกัด $-i$ นอกจากนี้ IOI-chan ผู้ถือธง อยู่ที่พิกัด $0$

ผู้เข้าแข่งขันแต่ละคนมีค่าที่เรียกว่า ความเชื่องช้า ผู้เข้าแข่งขันคนที่ $i$ มีความเชื่องช้า $D_i$ ผู้เข้าแข่งขันปฏิบัติตามกฎต่อไปนี้:

• ถ้าผู้เข้าแข่งขันคนที่ $i$ อยู่ห่างจากคนที่อยู่ข้างหน้าติดกัน (ผู้เข้าแข่งขันหรือ IOI-chan) เป็นระยะอย่างน้อย $D_i+1$ ผู้เข้าแข่งขันคนที่ $i$ จะเคลื่อนที่ไปยังตำแหน่งที่อยู่ห่างจากคนนั้นเป็นระยะ $1$ มิฉะนั้น ผู้เข้าแข่งขันคนที่ $i$ จะไม่เคลื่อนที่

IOI-chan เคลื่อนที่เป็นระยะ $1$ ในทิศบวกของเส้นจำนวนต่อหนึ่งหน่วยเวลา ผู้เข้าแข่งขันจะเคลื่อนที่ในทันทีเมื่อเงื่อนไขข้างต้นเป็นจริง

คุณเป็นผู้สื่อข่าวที่มารายงานพิธีเปิด คุณต้องถ่ายภาพ แต่กลับนอนหลับสนิทตลอดพิธี เมื่อไม่มีทางอื่น คุณจึงตัดสินใจโกงโดยถ่ายภาพสถานที่จัดงานแล้ววาดรูปผู้คนลงบนภาพเหล่านั้น

เพื่อไม่ให้ถูกจับได้ว่าโกง หรือเพื่อประมาณเวลาที่ใช้วาดรูป คุณต้องการทราบค่า $Q$ ค่าต่อไปนี้:

• จำนวนคนที่อยู่ ณ พิกัดระหว่าง $L_j$ ถึง $R_j$ รวมปลายทั้งสอง ณ เวลา $T_j$ ($1 \le j \le Q$)

งาน

เมื่อกำหนดความเชื่องช้าของผู้เข้าแข่งขันแต่ละคนและข้อมูลคำถาม $Q$ ข้อ จงเขียนโปรแกรมคำนวณจำนวนคนที่ตรงตามเงื่อนไขของคำถามแต่ละข้อ

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

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

• บรรทัดแรกมีจำนวนเต็มสองจำนวน $N$ และ $Q$ คั่นด้วยช่องว่าง หมายความว่ามีผู้เข้าแข่งขัน $N$ คน (ไม่รวม IOI-chan) และมีคำถาม $Q$ ข้อ
• บรรทัดที่ $i$ ($1 \le i \le N$) จาก $N$ บรรทัดถัดมา มีจำนวนเต็ม $D_i$ หมายความว่าผู้เข้าแข่งขันคนที่ $i$ จากด้านหน้ามีความเชื่องช้า $D_i$
• บรรทัดที่ $j$ ($1 \le j \le Q$) จาก $Q$ บรรทัดถัดมา มีจำนวนเต็มสามจำนวน $T_j$, $L_j$ และ $R_j$ คั่นด้วยช่องว่าง ค่าเหล่านี้แทนคำถามข้อที่ $j$

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

เขียน $Q$ บรรทัดไปยังข้อมูลส่งออกมาตรฐาน บรรทัดที่ $j$ ($1 \le j \le Q$) ต้องมีคำตอบของคำถามข้อที่ $j$

ข้อจำกัด

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

• $1 \le N \le 500\,000$
• $1 \le Q \le 500\,000$
• $1 \le D_i \le 1\,000\,000\,000$ ($1 \le i \le N$)
• $1 \le T_j \le 1\,000\,000\,000$ ($1 \le j \le Q$)
• $1 \le L_j \le R_j \le 1\,000\,000\,000$ ($1 \le j \le Q$)

งานย่อย

มีงานย่อย 3 งาน คะแนนและข้อจำกัดเพิ่มเติมของแต่ละงานย่อยมีดังต่อไปนี้:

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

• $D_i=1$ ($1 \le i \le N$)

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

• $N \le 1\,000$
• $Q \le 1\,000$
• $T_j \le 1\,000$ ($1 \le j \le Q$)
• $1 \le L_j \le R_j \le 1\,000$ ($1 \le j \le Q$)

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

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

ตัวอย่าง

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

3 6
2
5
3
1 2 4
2 2 4
3 2 4
4 2 4
5 2 4
6 2 4

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

0
1
1
2
1
2

หมายเหตุ

ในตัวอย่างนี้ ผู้เข้าแข่งขันและ IOI-chan เคลื่อนที่ดังต่อไปนี้

ต่อไปนี้ ช่วง $[L,R]$ หมายถึงเซตของจุดบนเส้นจำนวนที่มีพิกัดระหว่าง $L$ ถึง $R$ รวมปลายทั้งสอง

• ณ เวลา $0$ IOI-chan อยู่ที่พิกัด $0$ ผู้เข้าแข่งขันคนที่ 1, 2 และ 3 อยู่ที่พิกัด $-1$, $-2$ และ $-3$ ตามลำดับ
• ณ เวลา $1$ IOI-chan เคลื่อนที่ไปยังพิกัด $1$ ไม่มีผู้เข้าแข่งขันเคลื่อนที่ ผู้เข้าแข่งขันคนที่ 1, 2 และ 3 อยู่ที่พิกัด $-1$, $-2$ และ $-3$ ตามลำดับ เนื่องจากไม่มีคนอยู่ในช่วง $[2,4]$ จึงส่งออก 0 สำหรับคำถามข้อที่ 1
• ณ เวลา $2$ IOI-chan เคลื่อนที่ไปยังพิกัด $2$ ขณะนี้ระยะห่างระหว่าง IOI-chan กับผู้เข้าแข่งขันคนที่ 1 เท่ากับ $3$ ดังนั้นผู้เข้าแข่งขันคนที่ 1 จึงเคลื่อนที่ไปยังพิกัด $1$ ผู้เข้าแข่งขันคนที่ 1, 2 และ 3 อยู่ที่พิกัด $1$, $-2$ และ $-3$ ตามลำดับ เนื่องจากมีเพียง IOI-chan อยู่ในช่วง $[2,4]$ จึงส่งออก 1 สำหรับคำถามข้อที่ 2
• ณ เวลา $3$ IOI-chan เคลื่อนที่ไปยังพิกัด $3$ ไม่มีผู้เข้าแข่งขันเคลื่อนที่ ผู้เข้าแข่งขันคนที่ 1, 2 และ 3 อยู่ที่พิกัด $1$, $-2$ และ $-3$ ตามลำดับ เนื่องจากมีเพียง IOI-chan อยู่ในช่วง $[2,4]$ จึงส่งออก 1 สำหรับคำถามข้อที่ 3
• ณ เวลา $4$ IOI-chan เคลื่อนที่ไปยังพิกัด $4$ ขณะนี้ระยะห่างระหว่าง IOI-chan กับผู้เข้าแข่งขันคนที่ 1 เท่ากับ $3$ ดังนั้นผู้เข้าแข่งขันคนที่ 1 จึงเคลื่อนที่ไปยังพิกัด $3$ ผู้เข้าแข่งขันคนที่ 1, 2 และ 3 อยู่ที่พิกัด $3$, $-2$ และ $-3$ ตามลำดับ เนื่องจากมี IOI-chan และผู้เข้าแข่งขันคนที่ 1 อยู่ในช่วง $[2,4]$ จึงส่งออก 2 สำหรับคำถามข้อที่ 4
• ณ เวลา $5$ IOI-chan เคลื่อนที่ไปยังพิกัด $5$ ไม่มีผู้เข้าแข่งขันเคลื่อนที่ ผู้เข้าแข่งขันคนที่ 1, 2 และ 3 อยู่ที่พิกัด $3$, $-2$ และ $-3$ ตามลำดับ เนื่องจากมีเพียงผู้เข้าแข่งขันคนที่ 1 อยู่ในช่วง $[2,4]$ จึงส่งออก 1 สำหรับคำถามข้อที่ 5
• ณ เวลา $6$ IOI-chan เคลื่อนที่ไปยังพิกัด $6$ ขณะนี้ระยะห่างระหว่าง IOI-chan กับผู้เข้าแข่งขันคนที่ 1 เท่ากับ $3$ ดังนั้นผู้เข้าแข่งขันคนที่ 1 จึงเคลื่อนที่ไปยังพิกัด $5$ จากนั้นระยะห่างระหว่างผู้เข้าแข่งขันคนที่ 1 กับคนที่ 2 เท่ากับ $7$ ดังนั้นผู้เข้าแข่งขันคนที่ 2 จึงเคลื่อนที่ไปยังพิกัด $4$ นอกจากนี้ ระยะห่างระหว่างผู้เข้าแข่งขันคนที่ 2 กับคนที่ 3 เท่ากับ $7$ ดังนั้นผู้เข้าแข่งขันคนที่ 3 จึงเคลื่อนที่ไปยังพิกัด $3$ ผู้เข้าแข่งขันคนที่ 1, 2 และ 3 อยู่ที่พิกัด $5$, $4$ และ $3$ ตามลำดับ เนื่องจากมีผู้เข้าแข่งขันคนที่ 2 และ 3 อยู่ในช่วง $[2,4]$ จึงส่งออก 2 สำหรับคำถามข้อที่ 6

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

4 2
1
1
1
1
2 1 4
1 3 6

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

2
0

หมายเหตุ

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

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

6 6
11
36
28
80
98
66
36 29 33
190 171 210
18 20 100
1000 900 1100
92 87 99
200 100 300

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

1
6
0
5
2
7