Bitaro compró una larga brocheta de dangos para merendar. Esta brocheta puede representarse mediante $N$ enteros positivos $A_1,A_2,\ldots,A_N$ de la siguiente forma. Para cada entero $i$ con $0 \le i \le N$, sea $s_i=A_1+A_2+\cdots+A_i$. En particular, definimos $s_0=0$.

• La brocheta consta de $s_N$ dangos dispuestos en una sola columna, de arriba abajo.

• Cada dango es dulce o picante. El sabor de cada dango se describe así.

  • Si $i$ es un entero impar que satisface $1 \le i \le N$, los dangos desde la posición $s_{i-1}+1$ hasta la posición $s_i$, contando desde arriba, son dulces.
  • Si $i$ es un entero par que satisface $1 \le i \le N$, los dangos desde la posición $s_{i-1}+1$ hasta la posición $s_i$, contando desde arriba, son picantes.

Bitaro preparó $Q$ posibles planes para comer esta brocheta. El plan $j$ ($1 \le j \le Q$) está representado por los enteros $L_j,R_j$, que satisfacen $1 \le L_j \le R_j \le N$. En este plan come los dangos desde la posición $s_{L_j-1}+1$ hasta la posición $s_{R_j}$, contando desde arriba.

Además, Bitaro decidió dividir la brocheta en varios bocados de la siguiente manera. Aquí, $K$ es un entero positivo que representa su preferencia por el dulzor.

• Come los dangos de arriba abajo, y cada dango se come exactamente una vez.
• En un bocado puede comer cualquier cantidad positiva de dangos consecutivos de la brocheta. Si, entre los dangos de ese bocado, el número de dulces menos el número de picantes es al menos $K$, Bitaro queda satisfecho.

Dada la información sobre la brocheta y los planes, escribe un programa que calcule, para cada plan, el máximo número posible de veces que Bitaro puede quedar satisfecho.

Entrada

Lee los siguientes datos de la entrada estándar.

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

Salida

Escribe $Q$ líneas en la salida estándar. En la línea $j$ ($1 \le j \le Q$), escribe el máximo número de veces que Bitaro puede quedar satisfecho en el plan $j$.

Restricciones

• $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$).
• Todos los valores dados son enteros.

Subtareas

1. (6 puntos) $Q \le 10$.
2. (5 puntos) $K \le 2$.
3. (18 puntos) $K \le 10$.
4. (27 puntos) $A_1+A_2+\cdots+A_N \le 500\,000$.
5. (17 puntos) $N \le 200\,000$, $Q \le 200\,000$.
6. (27 puntos) No hay restricciones adicionales.

Ejemplos

Entrada 1

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

Salida 1

7
2

Nota

En el primer plan, Bitaro come los dangos desde el primero hasta el duodécimo, contando desde arriba. Comiendo repetidamente exactamente un dango por bocado desde arriba, puede quedar satisfecho $7$ veces. Como es imposible que quede satisfecho $8$ veces o más, debes escribir $7$.

En el segundo plan, Bitaro come los dangos desde el tercero hasta el noveno, contando desde arriba. Comiendo repetidamente exactamente un dango por bocado desde arriba, puede quedar satisfecho $2$ veces. Como es imposible que quede satisfecho $3$ veces o más, debes escribir $2$.

Esta entrada de ejemplo satisface las restricciones de todas las subtareas.

Entrada 2

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

Salida 2

2
0

Nota

Solo se diferencia de la entrada de ejemplo 1 en el valor de $K$.

En el primer plan, Bitaro puede quedar satisfecho $2$ veces comiendo los dangos en los siguientes cuatro bocados.

• En el primer bocado come los dangos del primero al quinto desde arriba. Como hay $4$ dangos dulces y $1$ picante, Bitaro queda satisfecho.
• En el segundo bocado come únicamente el sexto dango desde arriba. Como hay $0$ dangos dulces y $1$ picante, Bitaro no queda satisfecho.
• En el tercer bocado come los dangos del séptimo al noveno desde arriba. Como hay $0$ dangos dulces y $3$ picantes, Bitaro no queda satisfecho.
• En el cuarto bocado come los dangos del décimo al duodécimo desde arriba. Como hay $3$ dangos dulces y $0$ picantes, Bitaro queda satisfecho.

Como es imposible que quede satisfecho $3$ veces o más, debes escribir $2$.

En el segundo plan, es imposible comer los dangos de forma que Bitaro quede satisfecho al menos una vez, por lo que debes escribir $0$.

Esta entrada de ejemplo satisface las restricciones de las subtareas 1, 3, 4, 5, 6.

Entrada 3

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

Salida 3

3
2
1
1

Nota

Esta entrada de ejemplo satisface las restricciones de las subtareas 1, 4, 5, 6.