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$ הוא מספר שלם חיובי המייצג את העדפתו למתיקות.

• הוא אוכל את הכופתאות מלמעלה למטה, וכל כופתה נאכלת בדיוק פעם אחת.
• בכל נגיסה הוא יכול לאכול מספר חיובי כלשהו של כופתאות רצופות על השיפוד. אם מספר הכופתאות המתוקות פחות מספר הכופתאות החריפות שנאכלו באותה נגיסה הוא לפחות $K$, אז Bitaro מרוצה.

בהינתן המידע על שיפוד הכופתאות ועל התוכניות, כתוב תוכנית המחשבת לכל תוכנית את המספר המרבי של פעמים שבהן Bitaro יכול להיות מרוצה.

קלט

קרא את הנתונים הבאים מהקלט הסטנדרטי.

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

פלט

כתוב $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$.

בתוכנית השנייה Bitaro אוכל את הכופתאות מהשלישית ועד התשיעית מלמעלה. על ידי אכילת כופתה אחת בדיוק בכל נגיסה, מלמעלה, הוא יכול להיות מרוצה פעמיים. מאחר שאי אפשר לגרום לו להיות מרוצה שלוש פעמים או יותר, יש להדפיס $2$.

קלט זה מקיים את המגבלות של כל תתי־המשימות.

קלט 2

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

פלט 2

2
0

הסבר

הקלט הזה שונה מקלט לדוגמה 1 רק בערך $K$.

בתוכנית הראשונה Bitaro יכול להיות מרוצה פעמיים באמצעות אכילת הכופתאות בארבע הנגיסות הבאות.

• בנגיסה הראשונה הוא אוכל את הכופתאות מהראשונה עד החמישית מלמעלה. יש ארבע כופתאות מתוקות ואחת חריפה, ולכן Bitaro מרוצה.
• בנגיסה השנייה הוא אוכל רק את הכופתה השישית מלמעלה. יש אפס כופתאות מתוקות ואחת חריפה, ולכן Bitaro אינו מרוצה.
• בנגיסה השלישית הוא אוכל את הכופתאות מהשביעית עד התשיעית מלמעלה. יש אפס כופתאות מתוקות ושלוש חריפות, ולכן Bitaro אינו מרוצה.
• בנגיסה הרביעית הוא אוכל את הכופתאות מה־$10$ עד ה־$12$ מלמעלה. יש שלוש כופתאות מתוקות ואפס חריפות, ולכן Bitaro מרוצה.

מאחר שאי אפשר לגרום לו להיות מרוצה שלוש פעמים או יותר, יש להדפיס $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$.