Bitaro hat einen langen Spieß mit Klößchen als Zwischenmahlzeit gekauft. Dieser Spieß lässt sich wie folgt durch $N$ positive ganze Zahlen $A_1,A_2,\ldots,A_N$ darstellen. Für jede ganze Zahl $i$ mit $0 \le i \le N$ sei $s_i=A_1+A_2+\cdots+A_i$. Insbesondere definieren wir $s_0=0$.

• Der Spieß besteht aus $s_N$ Klößchen, die von oben nach unten in einer einzigen Spalte angeordnet sind.

• Jedes Klößchen ist entweder süß oder scharf. Der Geschmack jedes Klößchens lässt sich wie folgt beschreiben.

  • Ist $i$ eine ungerade ganze Zahl mit $1 \le i \le N$, so sind die Klößchen von der $(s_{i-1}+1)$-ten bis zur $s_i$-ten Position von oben süß.
  • Ist $i$ eine gerade ganze Zahl mit $1 \le i \le N$, so sind die Klößchen von der $(s_{i-1}+1)$-ten bis zur $s_i$-ten Position von oben scharf.

Für das Essen dieses Klößchenspießes hat Bitaro $Q$ mögliche Pläne erstellt. Der $j$-te Plan ($1 \le j \le Q$) wird durch ganze Zahlen $L_j$ und $R_j$ mit $1 \le L_j \le R_j \le N$ dargestellt. In diesem Plan isst er die Klößchen von der $(s_{L_j-1}+1)$-ten bis zur $s_{R_j}$-ten Position von oben.

Außerdem hat Bitaro beschlossen, den Spieß beim Essen auf die folgende Weise in mehrere Bissen aufzuteilen. Dabei ist $K$ eine positive ganze Zahl, die Bitaros Vorliebe für Süße beschreibt.

• Er isst die Klößchen von oben nach unten, und jedes Klößchen wird genau einmal gegessen.
• Mit einem Bissen darf er eine beliebige positive Anzahl aufeinanderfolgender Klößchen auf dem Spieß essen. Wenn unter den Klößchen dieses Bissens die Anzahl der süßen Klößchen minus der Anzahl der scharfen Klößchen mindestens $K$ beträgt, ist Bitaro zufrieden.

Schreibe ein Programm, das anhand der Informationen über den Klößchenspieß und die Pläne für jeden Plan berechnet, wie oft Bitaro höchstens zufrieden sein kann.

Eingabe

Lies die folgenden Daten von der Standardeingabe ein.

$$ \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} $$

Ausgabe

Schreibe $Q$ Zeilen auf die Standardausgabe. Gib in der $j$-ten Zeile ($1 \le j \le Q$) aus, wie oft Bitaro im $j$-ten Plan höchstens zufrieden sein kann.

Beschränkungen

• $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$).
• Alle gegebenen Werte sind ganze Zahlen.

Teilaufgaben

1. (6 Punkte) $Q \le 10$.
2. (5 Punkte) $K \le 2$.
3. (18 Punkte) $K \le 10$.
4. (27 Punkte) $A_1+A_2+\cdots+A_N \le 500\,000$.
5. (17 Punkte) $N \le 200\,000$, $Q \le 200\,000$.
6. (27 Punkte) Keine weiteren Beschränkungen.

Beispiele

Eingabe 1

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

Ausgabe 1

7
2

Hinweis

Im ersten Plan isst Bitaro die Klößchen von der ersten bis zur 12. Position von oben. Indem er von oben beginnend mit jedem Bissen genau ein Klößchen isst, kann Bitaro 7-mal zufrieden sein. Da es unmöglich ist, ihn 8-mal oder öfter zufriedenzustellen, sollst du 7 ausgeben.

Im zweiten Plan isst Bitaro die Klößchen von der dritten bis zur 9. Position von oben. Indem er von oben beginnend mit jedem Bissen genau ein Klößchen isst, kann Bitaro 2-mal zufrieden sein. Da es unmöglich ist, ihn 3-mal oder öfter zufriedenzustellen, sollst du 2 ausgeben.

Diese Beispieleingabe erfüllt die Beschränkungen aller Teilaufgaben.

Eingabe 2

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

Ausgabe 2

2
0

Hinweis

Diese Eingabe unterscheidet sich von Beispieleingabe 1 nur im Wert von $K$.

Im ersten Plan kann Bitaro 2-mal zufrieden sein, indem er die Klößchen in den folgenden vier Bissen isst.

• Beim ersten Bissen isst er die Klößchen von der ersten bis zur 5. Position von oben. Da es 4 süße Klößchen und 1 scharfes Klößchen sind, ist Bitaro zufrieden.
• Beim zweiten Bissen isst er nur das 6. Klößchen von oben. Da es 0 süße Klößchen und 1 scharfes Klößchen sind, ist Bitaro nicht zufrieden.
• Beim dritten Bissen isst er die Klößchen von der 7. bis zur 9. Position von oben. Da es 0 süße Klößchen und 3 scharfe Klößchen sind, ist Bitaro nicht zufrieden.
• Beim vierten Bissen isst er die Klößchen von der 10. bis zur 12. Position von oben. Da es 3 süße Klößchen und 0 scharfe Klößchen sind, ist Bitaro zufrieden.

Da es unmöglich ist, ihn 3-mal oder öfter zufriedenzustellen, sollst du 2 ausgeben.

Im zweiten Plan ist es unmöglich, dass Bitaro die Klößchen so isst, dass er auch nur einmal zufrieden ist. Deshalb sollst du 0 ausgeben.

Diese Beispieleingabe erfüllt die Beschränkungen der Teilaufgaben 1, 3, 4, 5 und 6.

Eingabe 3

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

Ausgabe 3

3
2
1
1

Hinweis

Diese Beispieleingabe erfüllt die Beschränkungen der Teilaufgaben 1, 4, 5 und 6.