Bitaro keypti sér langt spjót með soðkökum í nesti. Hægt er að lýsa þessu spjóti með $N$ jákvæðum heiltölum $A_1,A_2,\ldots,A_N$ sem hér segir. Fyrir hverja heiltölu $i$ þar sem $0\le i\le N$, látum $s_i=A_1+A_2+\cdots+A_i$. Sér í lagi skilgreinum við $s_0=0$.

• Spjótið samanstendur af $s_N$ soðkökum sem raðað er í eina röð ofan frá og niður.

• Hver soðkaka er annaðhvort sæt eða sterk. Lýsa má bragði hverrar soðköku sem hér segir.

  • Ef $i$ er oddatala sem uppfyllir $1\le i\le N$, þá eru soðkökurnar frá $(s_{i-1}+1)$-tu til $s_i$-tu að ofan sætar.
  • Ef $i$ er slétt tala sem uppfyllir $1\le i\le N$, þá eru soðkökurnar frá $(s_{i-1}+1)$-tu til $s_i$-tu að ofan sterkar.

Þegar Bitaro ætlar að borða þetta spjót af soðkökum gerði hann $Q$ mögulegar áætlanir. $j$-ta áætlunin ($1\le j\le Q$) er táknuð með heiltölum $L_j$ og $R_j$ sem uppfylla $1\le L_j\le R_j\le N$, og í þeirri áætlun borðar hann soðkökurnar frá $(s_{L_j-1}+1)$-tu að ofan til og með $s_{R_j}$-tu að ofan.

Einnig ákvað Bitaro að skipta spjótinu í nokkra munnbita á eftirfarandi hátt þegar hann borðar það. Hér er $K$ jákvæð heiltala sem táknar dálæti Bitaros á sætu bragði.

• Hann borðar soðkökurnar ofan frá og niður, og hver soðkaka er borðuð nákvæmlega einu sinni.
• Í einum munnbita má hann borða hvaða jákvæða fjölda sem er af samliggjandi soðkökum á spjótinu. Ef fjöldi sætra soðkaka að frádregnum fjölda sterkra soðkaka í þeim munnbita er að minnsta kosti $K$, þá verður Bitaro ánægður.

Gefnum upplýsingum um soðkökuspjótið og áætlanirnar, skrifið forrit sem reiknar fyrir hverja áætlun mesta mögulega fjölda skipta sem Bitaro getur orðið ánægður.

Inntak

Lesið eftirfarandi gögn úr staðalinntaki.

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

Úttak

Skrifið $Q$ línur í staðalúttak. Í $j$-tu línu ($1\le j\le Q$), skrifið út mesta fjölda skipta sem Bitaro getur orðið ánægður í $j$-tu áætluninni.

Skorður

• $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$).
• Öll gefin gildi eru heiltölur.

Undirverkefni

1. (6 stig) $Q\le10$.
2. (5 stig) $K\le2$.
3. (18 stig) $K\le10$.
4. (27 stig) $A_1+A_2+\cdots+A_N\le500\,000$.
5. (17 stig) $N\le200\,000$, $Q\le200\,000$.
6. (27 stig) Engar viðbótarskorður.

Dæmi

Inntak 1

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

Úttak 1

7
2

Athugasemd

Í fyrri áætluninni borðar Bitaro soðkökurnar frá þeirri fyrstu til og með þeirri 12. að ofan. Með því að borða endurtekið nákvæmlega eina soðköku í hverjum munnbita ofan frá getur Bitaro orðið ánægður 7 sinnum. Þar sem ómögulegt er að gera hann ánægðan 8 sinnum eða oftar ættir þú að skrifa út 7.

Í seinni áætluninni borðar Bitaro soðkökurnar frá þeirri þriðju til og með þeirri 9. að ofan. Með því að borða endurtekið nákvæmlega eina soðköku í hverjum munnbita ofan frá getur Bitaro orðið ánægður 2 sinnum. Þar sem ómögulegt er að gera hann ánægðan 3 sinnum eða oftar ættir þú að skrifa út 2.

Þetta sýniinntak uppfyllir skorður allra undirverkefna.

Inntak 2

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

Úttak 2

2
0

Athugasemd

Þetta er aðeins ólíkt Sýniinntaki 1 hvað varðar gildið á $K$.

Í fyrri áætluninni getur Bitaro orðið ánægður 2 sinnum með því að borða soðkökurnar í eftirfarandi fjórum munnbita.

• Í fyrsta munnbita borðar hann fyrstu til og með 5. soðkökuna að ofan. Þar sem fjöldi sætra soðkaka er 4 og fjöldi sterkra soðkaka er 1 verður Bitaro ánægður.
• Í öðrum munnbita borðar hann aðeins 6. soðkökuna að ofan. Þar sem fjöldi sætra soðkaka er 0 og fjöldi sterkra soðkaka er 1 verður Bitaro ekki ánægður.
• Í þriðja munnbita borðar hann 7. til og með 9. soðkökuna að ofan. Þar sem fjöldi sætra soðkaka er 0 og fjöldi sterkra soðkaka er 3 verður Bitaro ekki ánægður.
• Í fjórða munnbita borðar hann 10. til og með 12. soðkökuna að ofan. Þar sem fjöldi sætra soðkaka er 3 og fjöldi sterkra soðkaka er 0 verður Bitaro ánægður.

Þar sem ómögulegt er að gera hann ánægðan 3 sinnum eða oftar ættir þú að skrifa út 2.

Í seinni áætluninni er ómögulegt fyrir Bitaro að borða soðkökurnar þannig að hann verði ánægður að minnsta kosti einu sinni, svo þú ættir að skrifa út 0.

Þetta sýniinntak uppfyllir skorður undirverkefna $1,3,4,5,6$.

Inntak 3

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

Úttak 3

3
2
1
1

Athugasemd

Þetta sýniinntak uppfyllir skorður undirverkefna $1,4,5,6$.