Bitaro a acheté une longue brochette de boulettes pour son goûter. Cette brochette peut être représentée par $N$ entiers strictement positifs $A_1,A_2,\ldots,A_N$ de la manière suivante. Pour chaque entier $i$ tel que $0\le i\le N$, posons $s_i=A_1+A_2+\cdots+A_i$. En particulier, nous définissons $s_0=0$.

• La brochette comporte $s_N$ boulettes disposées en une seule colonne de haut en bas.

• Chaque boulette est soit sucrée, soit épicée. Le goût de chaque boulette peut être décrit comme suit.

  • Si $i$ est un entier impair vérifiant $1\le i\le N$, alors les boulettes de la $(s_{i-1}+1)$-ème à la $s_i$-ème en partant du haut sont sucrées.
  • Si $i$ est un entier pair vérifiant $1\le i\le N$, alors les boulettes de la $(s_{i-1}+1)$-ème à la $s_i$-ème en partant du haut sont épicées.

Pour manger cette brochette, Bitaro a élaboré $Q$ plans possibles. Le $j$-ème plan ($1\le j\le Q$) est représenté par les entiers $L_j$ et $R_j$ vérifiant $1\le L_j\le R_j\le N$. Dans ce plan, il mange les boulettes de la $(s_{L_j-1}+1)$-ème en partant du haut jusqu'à la $s_{R_j}$-ème en partant du haut.

Bitaro a également décidé de diviser la dégustation de cette brochette en plusieurs bouchées de la manière suivante. Ici, $K$ est un entier strictement positif représentant la préférence de Bitaro pour le sucré.

• Il mange les boulettes de haut en bas, et chaque boulette est mangée exactement une fois.
• En une bouchée, il peut manger un nombre strictement positif quelconque de boulettes consécutives sur la brochette. Si, parmi les boulettes mangées dans cette bouchée, le nombre de boulettes sucrées moins le nombre de boulettes épicées est au moins $K$, alors Bitaro est satisfait.

Écrivez un programme qui, à partir des informations sur la brochette et les plans, calcule pour chaque plan le nombre maximal de fois où Bitaro peut être satisfait.

Entrée

Lisez les données suivantes sur l'entrée standard.

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

Sortie

Écrivez $Q$ lignes sur la sortie standard. Sur la $j$-ème ligne ($1\le j\le Q$), affichez le nombre maximal de fois où Bitaro peut être satisfait dans le $j$-ème plan.

Contraintes

• $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$).
• Toutes les valeurs données sont des entiers.

Sous-tâches

1. (6 points) $Q\le10$.
2. (5 points) $K\le2$.
3. (18 points) $K\le10$.
4. (27 points) $A_1+A_2+\cdots+A_N\le500\,000$.
5. (17 points) $N\le200\,000$, $Q\le200\,000$.
6. (27 points) Aucune contrainte supplémentaire.

Exemples

Entrée 1

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

Sortie 1

7
2

Remarque

Pour le premier plan, Bitaro mange les boulettes de la première à la douzième en partant du haut. En mangeant successivement exactement une boulette par bouchée depuis le haut, Bitaro peut être satisfait 7 fois. Comme il est impossible de le satisfaire 8 fois ou plus, vous devez afficher 7.

Pour le deuxième plan, Bitaro mange les boulettes de la troisième à la neuvième en partant du haut. En mangeant successivement exactement une boulette par bouchée depuis le haut, Bitaro peut être satisfait 2 fois. Comme il est impossible de le satisfaire 3 fois ou plus, vous devez afficher 2.

Cet exemple d'entrée satisfait les contraintes de toutes les sous-tâches.

Entrée 2

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

Sortie 2

2
0

Remarque

Cet exemple ne diffère de l'exemple d'entrée 1 que par la valeur de $K$.

Pour le premier plan, Bitaro peut être satisfait 2 fois en mangeant les boulettes en quatre bouchées comme suit.

• Dans la première bouchée, il mange les boulettes de la première à la cinquième en partant du haut. Comme il y a 4 boulettes sucrées et 1 boulette épicée, Bitaro est satisfait.
• Dans la deuxième bouchée, il mange uniquement la sixième boulette en partant du haut. Comme il y a 0 boulette sucrée et 1 boulette épicée, Bitaro n'est pas satisfait.
• Dans la troisième bouchée, il mange les boulettes de la septième à la neuvième en partant du haut. Comme il y a 0 boulette sucrée et 3 boulettes épicées, Bitaro n'est pas satisfait.
• Dans la quatrième bouchée, il mange les boulettes de la dixième à la douzième en partant du haut. Comme il y a 3 boulettes sucrées et 0 boulette épicée, Bitaro est satisfait.

Comme il est impossible de le satisfaire 3 fois ou plus, vous devez afficher 2.

Pour le deuxième plan, il est impossible de manger les boulettes de manière à satisfaire Bitaro au moins une fois ; vous devez donc afficher 0.

Cet exemple d'entrée satisfait les contraintes des sous-tâches $1,3,4,5,6$.

Entrée 3

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

Sortie 3

3
2
1
1

Remarque

Cet exemple d'entrée satisfait les contraintes des sous-tâches $1,4,5,6$.