Bitaro ซื้อดังโงะเสียบไม้ยาวหนึ่งไม้มากินเป็นของว่าง ดังโงะไม้นี้สามารถอธิบายด้วยจำนวนเต็มบวก $N$ จำนวน $A_1,A_2,\ldots,A_N$ ได้ดังนี้ สำหรับจำนวนเต็ม $i$ แต่ละค่าที่ $0\le i\le N$ ให้ $s_i=A_1+A_2+\cdots+A_i$ โดยเฉพาะอย่างยิ่ง กำหนดให้ $s_0=0$

• บนไม้มีดังโงะ $s_N$ ลูกเรียงเป็นแถวเดียวจากบนลงล่าง

• ดังโงะแต่ละลูกมีรส หวาน หรือ เผ็ด รสชาติของดังโงะแต่ละลูกอธิบายได้ดังนี้

  • ถ้า $i$ เป็นจำนวนเต็มคี่ที่ $1\le i\le N$ ดังโงะตั้งแต่ลูกที่ $(s_{i-1}+1)$ ถึงลูกที่ $s_i$ เมื่อนับจากด้านบนจะมีรสหวาน
  • ถ้า $i$ เป็นจำนวนเต็มคู่ที่ $1\le i\le N$ ดังโงะตั้งแต่ลูกที่ $(s_{i-1}+1)$ ถึงลูกที่ $s_i$ เมื่อนับจากด้านบนจะมีรสเผ็ด

Bitaro คิดแผนที่เป็นไปได้ $Q$ แผนสำหรับการกินดังโงะไม้นี้ แผนที่ $j$ ($1\le j\le Q$) อธิบายด้วยจำนวนเต็ม $L_j$ และ $R_j$ ซึ่ง $1\le L_j\le R_j\le N$ และในแผนนี้เขาจะกินดังโงะตั้งแต่ลูกที่ $(s_{L_j-1}+1)$ จากด้านบนจนถึงลูกที่ $s_{R_j}$ จากด้านบน

นอกจากนี้ Bitaro ตัดสินใจแบ่งการกินดังโงะไม้นี้เป็นหลายคำตามวิธีต่อไปนี้ ในที่นี้ $K$ เป็นจำนวนเต็มบวกที่แสดงถึงความชอบรสหวานของ Bitaro

• เขากินดังโงะจากบนลงล่าง และดังโงะแต่ละลูกถูกกินเพียงครั้งเดียว
• ในหนึ่งคำ เขาสามารถกินดังโงะที่เรียงติดกันบนไม้เป็นจำนวนเต็มบวกเท่าใดก็ได้ ถ้าจำนวนดังโงะรสหวานลบด้วยจำนวนดังโงะรสเผ็ดในคำนั้นมีค่าอย่างน้อย $K$ แล้ว Bitaro จะรู้สึกพึงพอใจ

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

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

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

$$ \begin{array}{l} N\ Q\ K\\ A_1\ A_2\ \cdots\ A_N\\ L_1\ R_1\\ L_2\ R_2\\ \vdots\\ L_Q\ R_Q \end{array} $$

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

แสดงผล $Q$ บรรทัดไปยังข้อมูลส่งออกมาตรฐาน ในบรรทัดที่ $j$ ($1\le j\le Q$) แสดงจำนวนครั้งมากที่สุดที่ Bitaro สามารถรู้สึกพึงพอใจได้ในแผนที่ $j$

ข้อจำกัด

• $1\le N\le500\,000$
• $1\le Q\le500\,000$
• $1\le K\le10^{14}$
• $1\le A_i\le10^9$ ($1\le i\le N$)
• $1\le L_j\le R_j\le N$ ($1\le j\le Q$)
• ค่าที่ให้มาทั้งหมดเป็นจำนวนเต็ม

งานย่อย

1. (6 คะแนน) $Q\le10$
2. (5 คะแนน) $K\le2$
3. (18 คะแนน) $K\le10$
4. (27 คะแนน) $A_1+A_2+\cdots+A_N\le500\,000$
5. (17 คะแนน) $N\le200\,000$, $Q\le200\,000$
6. (27 คะแนน) ไม่มีข้อจำกัดเพิ่มเติม

ตัวอย่าง

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

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

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

7
2

หมายเหตุ

สำหรับแผนแรก Bitaro กินดังโงะตั้งแต่ลูกแรกถึงลูกที่ 12 จากด้านบน เมื่อกินจากด้านบนทีละหนึ่งลูกต่อคำ เขาสามารถรู้สึกพึงพอใจได้ 7 ครั้ง เนื่องจากไม่สามารถทำให้เขารู้สึกพึงพอใจตั้งแต่ 8 ครั้งขึ้นไปได้ จึงต้องแสดงผล 7

สำหรับแผนที่สอง Bitaro กินดังโงะตั้งแต่ลูกที่สามถึงลูกที่ 9 จากด้านบน เมื่อกินจากด้านบนทีละหนึ่งลูกต่อคำ เขาสามารถรู้สึกพึงพอใจได้ 2 ครั้ง เนื่องจากไม่สามารถทำให้เขารู้สึกพึงพอใจตั้งแต่ 3 ครั้งขึ้นไปได้ จึงต้องแสดงผล 2

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

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

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

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

2
0

หมายเหตุ

ข้อมูลนี้ต่างจากข้อมูลนำเข้าตัวอย่างที่ 1 เฉพาะค่า $K$ เท่านั้น

สำหรับแผนแรก Bitaro สามารถรู้สึกพึงพอใจได้ 2 ครั้งโดยแบ่งกินดังโงะเป็นสี่คำดังนี้

• ในคำแรก เขากินดังโงะตั้งแต่ลูกแรกถึงลูกที่ 5 จากด้านบน เนื่องจากมีดังโงะรสหวาน 4 ลูกและรสเผ็ด 1 ลูก Bitaro จึงรู้สึกพึงพอใจ
• ในคำที่สอง เขากินเฉพาะดังโงะลูกที่ 6 จากด้านบน เนื่องจากมีดังโงะรสหวาน 0 ลูกและรสเผ็ด 1 ลูก Bitaro จึงไม่รู้สึกพึงพอใจ
• ในคำที่สาม เขากินดังโงะตั้งแต่ลูกที่ 7 ถึงลูกที่ 9 จากด้านบน เนื่องจากมีดังโงะรสหวาน 0 ลูกและรสเผ็ด 3 ลูก Bitaro จึงไม่รู้สึกพึงพอใจ
• ในคำที่สี่ เขากินดังโงะตั้งแต่ลูกที่ 10 ถึงลูกที่ 12 จากด้านบน เนื่องจากมีดังโงะรสหวาน 3 ลูกและรสเผ็ด 0 ลูก Bitaro จึงรู้สึกพึงพอใจ

เนื่องจากไม่สามารถทำให้เขารู้สึกพึงพอใจตั้งแต่ 3 ครั้งขึ้นไปได้ จึงต้องแสดงผล 2

สำหรับแผนที่สอง ไม่มีวิธีกินดังโงะให้ Bitaro รู้สึกพึงพอใจอย่างน้อยหนึ่งครั้ง จึงต้องแสดงผล 0

ข้อมูลนำเข้าตัวอย่างนี้เป็นไปตามข้อจำกัดของงานย่อย $1,3,4,5,6$

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

9 4 50
24 26 89 45 84 72 15 31 66
1 9
2 8
4 6
5 6

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

3
2
1
1

หมายเหตุ

ข้อมูลนำเข้าตัวอย่างนี้เป็นไปตามข้อจำกัดของงานย่อย $1,4,5,6$