Bitaro osti välipalaksi pitkän mykyvartaan. Tämä varras voidaan esittää $N$ positiivisella kokonaisluvulla $A_1,A_2,\ldots,A_N$ seuraavasti. Olkoon jokaisella kokonaisluvulla $i$, jolle $0\le i\le N$, $s_i=A_1+A_2+\cdots+A_i$. Erityisesti määrittelemme $s_0=0$.

• Varras koostuu $s_N$ mykystä, jotka ovat yhdessä jonossa ylhäältä alas.

• Jokainen myky on joko makea tai tulinen. Kunkin mykyn maku määräytyy seuraavasti.

  • Jos $i$ on pariton kokonaisluku, jolle $1\le i\le N$, niin mykyt ylhäältä lukien $(s_{i-1}+1)$:nnestä $s_i$:nteen ovat makeita.
  • Jos $i$ on parillinen kokonaisluku, jolle $1\le i\le N$, niin mykyt ylhäältä lukien $(s_{i-1}+1)$:nnestä $s_i$:nteen ovat tulisia.

Syödessään tätä mykyvarrasta Bitaro laati $Q$ mahdollista suunnitelmaa. $j$:ttä suunnitelmaa ($1\le j\le Q$) kuvaavat kokonaisluvut $L_j$ ja $R_j$, joille pätee $1\le L_j\le R_j\le N$, ja tässä suunnitelmassa hän syö mykyt ylhäältä lukien $(s_{L_j-1}+1)$:nnestä aina ylhäältä lukien $s_{R_j}$:nteen saakka.

Lisäksi syödessään tätä varrasta Bitaro päätti jakaa sen useaan suupalaan seuraavalla tavalla. Tässä $K$ on positiivinen kokonaisluku, joka kuvaa Bitaron mieltymystä makeaan.

• Hän syö mykyt ylhäältä alas, ja jokainen myky syödään täsmälleen kerran.
• Yhdellä suupalalla hän voi syödä minkä tahansa positiivisen määrän vartaassa peräkkäin olevia mykyjä. Jos kyseisellä suupalalla syötyjen mykyjen joukossa makeiden mykyjen lukumäärä miinus tulisten mykyjen lukumäärä on vähintään $K$, Bitaro tulee tyytyväiseksi.

Kirjoita ohjelma, joka saa syötteenä tiedot mykyvartaasta ja suunnitelmista ja laskee jokaiselle suunnitelmalle, kuinka monta kertaa Bitaro voi enintään tulla tyytyväiseksi.

Syöte

Lue seuraavat tiedot vakiosyötteestä.

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

Tuloste

Kirjoita $Q$ riviä vakiotulosteeseen. Tulosta $j$:nnelle riville ($1\le j\le Q$) suurin mahdollinen määrä kertoja, jonka Bitaro voi tulla tyytyväiseksi $j$:nnessä suunnitelmassa.

Rajoitukset

• $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$).
• Kaikki annetut arvot ovat kokonaislukuja.

Osatehtävät

1. (6 pistettä) $Q\le10$.
2. (5 pistettä) $K\le2$.
3. (18 pistettä) $K\le10$.
4. (27 pistettä) $A_1+A_2+\cdots+A_N\le500\,000$.
5. (17 pistettä) $N\le200\,000$, $Q\le200\,000$.
6. (27 pistettä) Ei lisärajoituksia.

Esimerkit

Syöte 1

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

Tuloste 1

7
2

Huomautus

Ensimmäisessä suunnitelmassa Bitaro syö mykyt ensimmäisestä 12:nteen ylhäältä lukien. Syömällä toistuvasti täsmälleen yhden mykyn suupalaa kohti ylhäältä alkaen Bitaro voi tulla tyytyväiseksi 7 kertaa. Koska on mahdotonta saada häntä tyytyväiseksi 8 kertaa tai useammin, tulee tulostaa 7.

Toisessa suunnitelmassa Bitaro syö mykyt kolmannesta 9:nteen ylhäältä lukien. Syömällä toistuvasti täsmälleen yhden mykyn suupalaa kohti ylhäältä alkaen Bitaro voi tulla tyytyväiseksi 2 kertaa. Koska on mahdotonta saada häntä tyytyväiseksi 3 kertaa tai useammin, tulee tulostaa 2.

Tämä esimerkkisyöte täyttää kaikkien osatehtävien rajoitukset.

Syöte 2

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

Tuloste 2

2
0

Huomautus

Tämä eroaa esimerkkisyötteestä 1 vain luvun $K$ arvon osalta.

Ensimmäisessä suunnitelmassa Bitaro voi tulla tyytyväiseksi 2 kertaa syömällä mykyt seuraavina neljänä suupalana.

• Ensimmäisellä suupalalla hän syö mykyt ensimmäisestä 5:nteen ylhäältä lukien. Koska makeita mykyjä on 4 ja tulisia mykyjä on 1, Bitaro tulee tyytyväiseksi.
• Toisella suupalalla hän syö vain 6:nnen mykyn ylhäältä lukien. Koska makeita mykyjä on 0 ja tulisia mykyjä on 1, Bitaro ei tule tyytyväiseksi.
• Kolmannella suupalalla hän syö mykyt 7:nnestä 9:nteen ylhäältä lukien. Koska makeita mykyjä on 0 ja tulisia mykyjä on 3, Bitaro ei tule tyytyväiseksi.
• Neljännellä suupalalla hän syö mykyt 10:nnestä 12:nteen ylhäältä lukien. Koska makeita mykyjä on 3 ja tulisia mykyjä on 0, Bitaro tulee tyytyväiseksi.

Koska on mahdotonta saada häntä tyytyväiseksi 3 kertaa tai useammin, tulee tulostaa 2.

Toisessa suunnitelmassa Bitaron on mahdotonta syödä mykyjä siten, että hän tulisi tyytyväiseksi vähintään kerran, joten tulee tulostaa 0.

Tämä esimerkkisyöte täyttää osatehtävien $1,3,4,5,6$ rajoitukset.

Syöte 3

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

Tuloste 3

3
2
1
1

Huomautus

Tämä esimerkkisyöte täyttää osatehtävien $1,4,5,6$ rajoitukset.