Bitaro kjøpte et langt spyd med melboller som mellommåltid. Dette spydet kan representeres av $N$ positive heltall $A_1,A_2,\ldots,A_N$ på følgende måte. For hvert heltall $i$ med $0\le i\le N$, la $s_i=A_1+A_2+\cdots+A_i$. Spesielt definerer vi $s_0=0$.

• Spydet består av $s_N$ melboller plassert i én enkelt kolonne ovenfra og ned.

• Hver melbolle er enten søt eller sterk. Smaken på hver melbolle kan beskrives som følger.

  • Hvis $i$ er et odde heltall som oppfyller $1\le i\le N$, er melbollene fra den $(s_{i-1}+1)$-te til den $s_i$-te ovenfra søte.
  • Hvis $i$ er et partall som oppfyller $1\le i\le N$, er melbollene fra den $(s_{i-1}+1)$-te til den $s_i$-te ovenfra sterke.

Når Bitaro skal spise dette spydet med melboller, har han laget $Q$ mulige planer. Den $j$-te planen ($1\le j\le Q$) er representert ved heltallene $L_j$ og $R_j$ som oppfyller $1\le L_j\le R_j\le N$, og i denne planen spiser han melbollene fra den $(s_{L_j-1}+1)$-te ovenfra til og med den $s_{R_j}$-te ovenfra.

Når han spiser dette spydet, bestemte Bitaro seg også for å dele det opp i flere munnfuller på følgende måte. Her er $K$ et positivt heltall som representerer Bitaros preferanse for sødme.

• Han spiser melbollene ovenfra og ned, og hver melbolle spises nøyaktig én gang.
• I én munnfull kan han spise et hvilket som helst positivt antall påfølgende melboller på spydet. Hvis antallet søte melboller minus antallet sterke melboller blant melbollene som spises i den munnfullen er minst $K$, blir Bitaro fornøyd.

Gitt informasjonen om spydet med melboller og planene, skriv et program som for hver plan beregner det maksimale antallet ganger Bitaro kan bli fornøyd.

Inndata

Les følgende data fra standard inndata.

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

Utdata

Skriv $Q$ linjer til standard utdata. På den $j$-te linjen ($1\le j\le Q$) skal du skrive ut det maksimale antallet ganger Bitaro kan bli fornøyd i den $j$-te planen.

Begrensninger

• $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$).
• Alle oppgitte verdier er heltall.

Deloppgaver

1. (6 poeng) $Q\le10$.
2. (5 poeng) $K\le2$.
3. (18 poeng) $K\le10$.
4. (27 poeng) $A_1+A_2+\cdots+A_N\le500\,000$.
5. (17 poeng) $N\le200\,000$, $Q\le200\,000$.
6. (27 poeng) Ingen ytterligere begrensninger.

Eksempler

Inndata 1

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

Utdata 1

7
2

Forklaring

For den første planen spiser Bitaro melbollene fra den første til og med den 12. ovenfra. Ved å gjentatte ganger spise nøyaktig én melbolle per munnfull ovenfra, kan Bitaro bli fornøyd 7 ganger. Siden det er umulig å gjøre ham fornøyd 8 ganger eller mer, skal du skrive ut 7.

For den andre planen spiser Bitaro melbollene fra den tredje til og med den 9. ovenfra. Ved å gjentatte ganger spise nøyaktig én melbolle per munnfull ovenfra, kan Bitaro bli fornøyd 2 ganger. Siden det er umulig å gjøre ham fornøyd 3 ganger eller mer, skal du skrive ut 2.

Disse eksempeldataene oppfyller begrensningene i alle deloppgavene.

Inndata 2

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

Utdata 2

2
0

Forklaring

Dette skiller seg fra Eksempelinndata 1 bare i verdien av $K$.

For den første planen kan Bitaro bli fornøyd 2 ganger ved å spise melbollene i følgende fire munnfuller.

• I den første munnfullen spiser han den første til og med den 5. melbollen ovenfra. Siden antallet søte melboller er 4 og antallet sterke melboller er 1, blir Bitaro fornøyd.
• I den andre munnfullen spiser han bare den 6. melbollen ovenfra. Siden antallet søte melboller er 0 og antallet sterke melboller er 1, blir ikke Bitaro fornøyd.
• I den tredje munnfullen spiser han den 7. til og med den 9. melbollen ovenfra. Siden antallet søte melboller er 0 og antallet sterke melboller er 3, blir ikke Bitaro fornøyd.
• I den fjerde munnfullen spiser han den 10. til og med den 12. melbollen ovenfra. Siden antallet søte melboller er 3 og antallet sterke melboller er 0, blir Bitaro fornøyd.

Siden det er umulig å gjøre ham fornøyd 3 ganger eller mer, skal du skrive ut 2.

For den andre planen er det umulig for Bitaro å spise melbollene på en slik måte at han blir fornøyd minst én gang, så du skal skrive ut 0.

Disse eksempeldataene oppfyller begrensningene i deloppgavene $1,3,4,5,6$.

Inndata 3

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

Utdata 3

3
2
1
1

Forklaring

Disse eksempeldataene oppfyller begrensningene i deloppgavene $1,4,5,6$.