اشترى 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\quad Q\quad K\\ A_1\quad A_2\quad\cdots\quad A_N\\ L_1\quad R_1\\ L_2\quad R_2\\ \vdots\\ L_Q\quad R_Q \end{gathered} $$

الإخراج

اكتب $Q$ سطرًا إلى الإخراج القياسي. في السطر $j$، حيث $1 \le j \le Q$، أخرج أكبر عدد من المرات التي يمكن أن يشعر فيها Bitaro بالرضا في الخطة $j$.

القيود

• $1 \le N \le 500\,000$.
• $1 \le Q \le 500\,000$.
• $1 \le K \le 10^{14}$.
• $1 \le A_i \le 10^9$، حيث $1 \le i \le N$.
• $1 \le L_j \le R_j \le N$، حيث $1 \le j \le Q$.
• جميع القيم المعطاة أعداد صحيحة.

المهام الفرعية

1. (6 نقاط) $Q \le 10$.
2. (5 نقاط) $K \le 2$.
3. (18 نقطة) $K \le 10$.
4. (27 نقطة) $A_1+A_2+\cdots+A_N \le 500\,000$.
5. (17 نقطة) $N \le 200\,000$ و$Q \le 200\,000$.
6. (27 نقطة) لا توجد قيود إضافية.

أمثلة

الإدخال 1

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

الإخراج 1

7
2

ملاحظة

في الخطة الأولى، يأكل Bitaro الكرات من الأولى إلى الثانية عشرة عند العد من الأعلى. بتناول كرة واحدة بالضبط في كل قضمة تباعًا من الأعلى، يمكنه الشعور بالرضا $7$ مرات. وبما أنه يستحيل أن يشعر بالرضا $8$ مرات أو أكثر، فيجب إخراج $7$.

في الخطة الثانية، يأكل Bitaro الكرات من الثالثة إلى التاسعة عند العد من الأعلى. بتناول كرة واحدة بالضبط في كل قضمة تباعًا من الأعلى، يمكنه الشعور بالرضا مرتين. وبما أنه يستحيل أن يشعر بالرضا $3$ مرات أو أكثر، فيجب إخراج $2$.

يستوفي مثال الإدخال هذا قيود جميع المهام الفرعية.

الإدخال 2

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

الإخراج 2

2
0

ملاحظة

يختلف هذا عن مثال الإدخال 1 في قيمة $K$ فقط.

في الخطة الأولى، يمكن أن يشعر Bitaro بالرضا مرتين بتناول الكرات في القضمات الأربع التالية.

• في القضمة الأولى، يأكل الكرات من الأولى إلى الخامسة عند العد من الأعلى. ولأن عدد الكرات الحلوة $4$ وعدد الحارة $1$، يشعر Bitaro بالرضا.
• في القضمة الثانية، يأكل الكرة السادسة فقط عند العد من الأعلى. ولأن عدد الكرات الحلوة $0$ وعدد الحارة $1$، لا يشعر Bitaro بالرضا.
• في القضمة الثالثة، يأكل الكرات من السابعة إلى التاسعة عند العد من الأعلى. ولأن عدد الكرات الحلوة $0$ وعدد الحارة $3$، لا يشعر Bitaro بالرضا.
• في القضمة الرابعة، يأكل الكرات من العاشرة إلى الثانية عشرة عند العد من الأعلى. ولأن عدد الكرات الحلوة $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.