Bitaro comprou um longo espeto de bolinhos para comer como lanche. Esse espeto pode ser representado por $N$ inteiros positivos $A_1,A_2,\ldots,A_N$ da seguinte forma. Para cada inteiro $i$ com $0 \le i \le N$, seja $s_i=A_1+A_2+\cdots+A_i$. Em particular, definimos $s_0=0$.

• O espeto consiste em $s_N$ bolinhos dispostos em uma única coluna, de cima para baixo.

• Cada bolinho é doce ou picante. O sabor de cada bolinho pode ser descrito da seguinte forma.

  • Se $i$ é um inteiro ímpar que satisfaz $1 \le i \le N$, os bolinhos da posição $(s_{i-1}+1)$ até a posição $s_i$, contadas de cima para baixo, são doces.
  • Se $i$ é um inteiro par que satisfaz $1 \le i \le N$, os bolinhos da posição $(s_{i-1}+1)$ até a posição $s_i$, contadas de cima para baixo, são picantes.

Para comer esse espeto de bolinhos, Bitaro elaborou $Q$ planos possíveis. O $j$-ésimo plano ($1 \le j \le Q$) é representado pelos inteiros $L_j$ e $R_j$, que satisfazem $1 \le L_j \le R_j \le N$, e nesse plano ele come os bolinhos da posição $(s_{L_j-1}+1)$ até a posição $s_{R_j}$, contadas de cima para baixo.

Além disso, ao comer esse espeto, Bitaro decidiu dividi-lo em várias bocadas da maneira a seguir. Aqui, $K$ é um inteiro positivo que representa a preferência de Bitaro por doçura.

• Ele come os bolinhos de cima para baixo, e cada bolinho é comido exatamente uma vez.
• Em uma bocada, ele pode comer qualquer quantidade positiva de bolinhos consecutivos do espeto. Se, entre os bolinhos comidos nessa bocada, o número de bolinhos doces menos o número de bolinhos picantes for pelo menos $K$, Bitaro fica satisfeito.

Dadas as informações sobre o espeto de bolinhos e os planos, escreva um programa que calcule, para cada plano, o maior número possível de vezes que Bitaro pode ficar satisfeito.

Entrada

Leia os seguintes dados da entrada padrão.

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

Saída

Escreva $Q$ linhas na saída padrão. Na $j$-ésima linha ($1 \le j \le Q$), imprima o maior número de vezes que Bitaro pode ficar satisfeito no $j$-ésimo plano.

Restrições

• $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 os valores fornecidos são inteiros.

Subtarefas

1. (6 pontos) $Q \le 10$.
2. (5 pontos) $K \le 2$.
3. (18 pontos) $K \le 10$.
4. (27 pontos) $A_1+A_2+\cdots+A_N \le 500\,000$.
5. (17 pontos) $N \le 200\,000$, $Q \le 200\,000$.
6. (27 pontos) Não há restrições adicionais.

Exemplos

Entrada 1

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

Saída 1

7
2

Explicação

No primeiro plano, Bitaro come os bolinhos da primeira até a 12ª posição, contadas de cima para baixo. Comendo repetidamente exatamente um bolinho por bocada a partir do topo, Bitaro pode ficar satisfeito 7 vezes. Como é impossível fazê-lo ficar satisfeito 8 vezes ou mais, você deve imprimir 7.

No segundo plano, Bitaro come os bolinhos da terceira até a 9ª posição, contadas de cima para baixo. Comendo repetidamente exatamente um bolinho por bocada a partir do topo, Bitaro pode ficar satisfeito 2 vezes. Como é impossível fazê-lo ficar satisfeito 3 vezes ou mais, você deve imprimir 2.

Este exemplo de entrada satisfaz as restrições de todas as subtarefas.

Entrada 2

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

Saída 2

2
0

Explicação

Este exemplo difere do Exemplo de Entrada 1 apenas no valor de $K$.

No primeiro plano, Bitaro pode ficar satisfeito 2 vezes comendo os bolinhos nas quatro bocadas a seguir.

• Na primeira bocada, ele come os bolinhos da primeira até a 5ª posição, contadas de cima para baixo. Como há 4 bolinhos doces e 1 picante, Bitaro fica satisfeito.
• Na segunda bocada, ele come apenas o 6º bolinho a partir do topo. Como há 0 bolinhos doces e 1 picante, Bitaro não fica satisfeito.
• Na terceira bocada, ele come os bolinhos da 7ª até a 9ª posição, contadas de cima para baixo. Como há 0 bolinhos doces e 3 picantes, Bitaro não fica satisfeito.
• Na quarta bocada, ele come os bolinhos da 10ª até a 12ª posição, contadas de cima para baixo. Como há 3 bolinhos doces e 0 picantes, Bitaro fica satisfeito.

Como é impossível fazê-lo ficar satisfeito 3 vezes ou mais, você deve imprimir 2.

No segundo plano, é impossível que Bitaro coma os bolinhos de forma a ficar satisfeito pelo menos uma vez, portanto você deve imprimir 0.

Este exemplo de entrada satisfaz as restrições das subtarefas 1, 3, 4, 5 e 6.

Entrada 3

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

Saída 3

3
2
1
1

Explicação

Este exemplo de entrada satisfaz as restrições das subtarefas 1, 4, 5 e 6.