Bitaro köpte ett långt spett med degknyten som mellanmål. Detta spett kan representeras av $N$ positiva heltal $A_1,A_2,\ldots,A_N$ enligt följande. För varje heltal $i$ med $0\le i\le N$, låt $s_i=A_1+A_2+\cdots+A_i$. Speciellt definierar vi $s_0=0$.

• Spettet består av $s_N$ degknyten ordnade i en enda kolumn uppifrån och ner.

• Varje degknyte är antingen sött eller kryddstarkt. Smaken på varje degknyte kan beskrivas på följande sätt.

  • Om $i$ är ett udda heltal som uppfyller $1\le i\le N$, är degknytena från det $(s_{i-1}+1)$:te till det $s_i$:te uppifrån söta.
  • Om $i$ är ett jämnt heltal som uppfyller $1\le i\le N$, är degknytena från det $(s_{i-1}+1)$:te till det $s_i$:te uppifrån kryddstarka.

När Bitaro skulle äta detta spett med degknyten gjorde han upp $Q$ möjliga planer. Den $j$:te planen ($1\le j\le Q$) representeras av heltal $L_j$ och $R_j$ som uppfyller $1\le L_j\le R_j\le N$, och i denna plan äter han degknytena från det $(s_{L_j-1}+1)$:te uppifrån till och med det $s_{R_j}$:te uppifrån.

När Bitaro äter detta spett bestämde han sig också för att dela upp det i flera tuggor på följande sätt. Här är $K$ ett positivt heltal som representerar Bitaros förkärlek för sötma.

• Han äter degknytena uppifrån och ner, och varje degknyte äts exakt en gång.
• I en tugga kan han äta valfritt positivt antal på varandra följande degknyten på spettet. Om antalet söta degknyten minus antalet kryddstarka degknyten bland de degknyten som äts i den tuggan är minst $K$, blir Bitaro nöjd.

Givet informationen om spettet med degknyten och planerna, skriv ett program som för varje plan beräknar det största möjliga antalet gånger som Bitaro kan bli nöjd.

Indata

Läs följande data från standard in.

$$ \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$ rader till standard ut. På den $j$:te raden ($1\le j\le Q$), skriv ut det största antalet gånger som Bitaro kan bli nöjd i den $j$:te planen.

Begränsningar

• $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$).
• Alla givna värden är heltal.

Deluppgifter

1. (6 poäng) $Q\le10$.
2. (5 poäng) $K\le2$.
3. (18 poäng) $K\le10$.
4. (27 poäng) $A_1+A_2+\cdots+A_N\le500\,000$.
5. (17 poäng) $N\le200\,000$, $Q\le200\,000$.
6. (27 poäng) Inga ytterligare begränsningar.

Exempel

Indata 1

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

Utdata 1

7
2

Förklaring

För den första planen äter Bitaro degknytena från det första till och med det 12:e uppifrån. Genom att upprepade gånger äta exakt ett degknyte per tugga uppifrån kan Bitaro bli nöjd 7 gånger. Eftersom det är omöjligt att få honom nöjd 8 gånger eller fler ska du skriva ut 7.

För den andra planen äter Bitaro degknytena från det tredje till och med det 9:e uppifrån. Genom att upprepade gånger äta exakt ett degknyte per tugga uppifrån kan Bitaro bli nöjd 2 gånger. Eftersom det är omöjligt att få honom nöjd 3 gånger eller fler ska du skriva ut 2.

Detta exempelindata uppfyller begränsningarna för alla deluppgifter.

Indata 2

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

Utdata 2

2
0

Förklaring

Detta skiljer sig från Exempelindata 1 endast i värdet på $K$.

För den första planen kan Bitaro bli nöjd 2 gånger genom att äta degknytena i följande fyra tuggor.

• I den första tuggan äter han det första till och med det 5:e degknytet uppifrån. Eftersom antalet söta degknyten är 4 och antalet kryddstarka degknyten är 1 blir Bitaro nöjd.
• I den andra tuggan äter han endast det 6:e degknytet uppifrån. Eftersom antalet söta degknyten är 0 och antalet kryddstarka degknyten är 1 blir Bitaro inte nöjd.
• I den tredje tuggan äter han det 7:e till och med det 9:e degknytet uppifrån. Eftersom antalet söta degknyten är 0 och antalet kryddstarka degknyten är 3 blir Bitaro inte nöjd.
• I den fjärde tuggan äter han det 10:e till och med det 12:e degknytet uppifrån. Eftersom antalet söta degknyten är 3 och antalet kryddstarka degknyten är 0 blir Bitaro nöjd.

Eftersom det är omöjligt att få honom nöjd 3 gånger eller fler ska du skriva ut 2.

För den andra planen är det omöjligt för Bitaro att äta degknytena på ett sådant sätt att han blir nöjd minst en gång, så du ska skriva ut 0.

Detta exempelindata uppfyller begränsningarna för deluppgifterna $1,3,4,5,6$.

Indata 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

Förklaring

Detta exempelindata uppfyller begränsningarna för deluppgifterna $1,4,5,6$.