Bitaro ha comprato un lungo spiedino di ravioli come spuntino. Questo spiedino può essere rappresentato da $N$ numeri interi positivi $A_1,A_2,\ldots,A_N$ come segue. Per ogni numero intero $i$ con $0\le i\le N$, sia $s_i=A_1+A_2+\cdots+A_i$. In particolare, definiamo $s_0=0$.

• Lo spiedino è composto da $s_N$ ravioli disposti in un'unica colonna dall'alto verso il basso.

• Ogni raviolo è dolce oppure piccante. Il sapore di ciascun raviolo può essere descritto come segue.

  • Se $i$ è un intero dispari che soddisfa $1\le i\le N$, allora i ravioli dal $(s_{i-1}+1)$-esimo al $s_i$-esimo dall'alto sono dolci.
  • Se $i$ è un intero pari che soddisfa $1\le i\le N$, allora i ravioli dal $(s_{i-1}+1)$-esimo al $s_i$-esimo dall'alto sono piccanti.

Per mangiare questo spiedino di ravioli, Bitaro ha preparato $Q$ possibili piani. Il $j$-esimo piano ($1\le j\le Q$) è rappresentato da numeri interi $L_j$ e $R_j$ che soddisfano $1\le L_j\le R_j\le N$, e in questo piano egli mangia i ravioli dal $(s_{L_j-1}+1)$-esimo dall'alto fino al $s_{R_j}$-esimo dall'alto.

Inoltre, nel mangiare questo spiedino, Bitaro ha deciso di dividerlo in diversi bocconi nel modo seguente. Qui, $K$ è un intero positivo che rappresenta la preferenza di Bitaro per il dolce.

• Egli mangia i ravioli dall'alto verso il basso, e ogni raviolo viene mangiato esattamente una volta.
• In un singolo boccone, può mangiare un qualsiasi numero positivo di ravioli consecutivi sullo spiedino. Se, tra i ravioli mangiati in quel boccone, il numero di ravioli dolci meno il numero di ravioli piccanti è almeno $K$, allora Bitaro è soddisfatto.

Date le informazioni sullo spiedino di ravioli e sui piani, scrivi un programma che, per ciascun piano, calcoli il massimo numero possibile di volte in cui Bitaro può essere soddisfatto.

Input

Leggi i seguenti dati dallo standard input.

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

Output

Scrivi $Q$ righe sullo standard output. Nella $j$-esima riga ($1\le j\le Q$), stampa il massimo numero di volte in cui Bitaro può essere soddisfatto nel $j$-esimo piano.

Vincoli

• $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$).
• I valori forniti sono tutti numeri interi.

Subtask

1. (6 punti) $Q\le10$.
2. (5 punti) $K\le2$.
3. (18 punti) $K\le10$.
4. (27 punti) $A_1+A_2+\cdots+A_N\le500\,000$.
5. (17 punti) $N\le200\,000$, $Q\le200\,000$.
6. (27 punti) Nessun vincolo aggiuntivo.

Esempi

Input 1

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

Output 1

7
2

Nota

Per il primo piano, Bitaro mangia i ravioli dal primo al 12-esimo dall'alto. Mangiando ripetutamente esattamente un raviolo per boccone partendo dall'alto, Bitaro può essere soddisfatto 7 volte. Poiché è impossibile renderlo soddisfatto 8 o più volte, bisogna stampare 7.

Per il secondo piano, Bitaro mangia i ravioli dal terzo al 9-o dall'alto. Mangiando ripetutamente esattamente un raviolo per boccone partendo dall'alto, Bitaro può essere soddisfatto 2 volte. Poiché è impossibile renderlo soddisfatto 3 o più volte, bisogna stampare 2.

Questo input di esempio soddisfa i vincoli di tutti i subtask.

Input 2

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

Output 2

2
0

Nota

Questo esempio differisce dall'Input di esempio 1 solo per il valore di $K$.

Per il primo piano, Bitaro può essere soddisfatto 2 volte mangiando i ravioli nei seguenti quattro bocconi.

• Nel primo boccone, mangia i ravioli dal primo al 5-o dall'alto. Poiché il numero di ravioli dolci è 4 e il numero di ravioli piccanti è 1, Bitaro è soddisfatto.
• Nel secondo boccone, mangia solo il 6-o raviolo dall'alto. Poiché il numero di ravioli dolci è 0 e il numero di ravioli piccanti è 1, Bitaro non è soddisfatto.
• Nel terzo boccone, mangia i ravioli dal 7-o al 9-o dall'alto. Poiché il numero di ravioli dolci è 0 e il numero di ravioli piccanti è 3, Bitaro non è soddisfatto.
• Nel quarto boccone, mangia i ravioli dal 10-o al 12-esimo dall'alto. Poiché il numero di ravioli dolci è 3 e il numero di ravioli piccanti è 0, Bitaro è soddisfatto.

Poiché è impossibile renderlo soddisfatto 3 o più volte, bisogna stampare 2.

Per il secondo piano, è impossibile per Bitaro mangiare i ravioli in modo da essere soddisfatto almeno una volta, quindi bisogna stampare 0.

Questo input di esempio soddisfa i vincoli dei subtask $1,3,4,5,6$.

Input 3

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

Output 3

3
2
1
1

Nota

Questo input di esempio soddisfa i vincoli dei subtask $1,4,5,6$.