Du har evnen til å lage roboter med høyde i intervallet $[0, d]$. For å teste dem har du bygget en linje med lengde $n$ som inneholder noen hindringer. Beskrivelsen av hindringene er gitt som en tabell $a$. Hvis $a_i = 0$, er det ingen hindring på den $i$-te posisjonen, og ellers er det en hindring med høyde $a_i > 0$.

For å teste roboten din velger du et segment $[l, r]$ og kjører den gjennom alle hindringene i segmentet. Når roboten møter en hindring med verdi $a_i > 0$, skjer ett av to mulige utfall:

• Hvis den nåværende høyden til roboten $h$ er mindre enn $a_i$, skjer det ingenting siden roboten er for lav til å nå opp til hindringen.
• Hvis den nåværende høyden til roboten $h$ er minst $a_i$, endres den nye høyden til $h' = h - a_i$.

Nå må du svare på $q$ spørringer. For hvert av de $q$ segmentene $[l_i, r_i]$ må du oppgi den maksimalt mulige høyden roboten kan ende opp med etter å ha kjørt gjennom hindringene i segmentet dersom starthøyden ble valgt fra intervallet $[0, d]$.

Inndata

Første linje inneholder heltallene $n, q, d$ ($1 \le n, q \le 3 \cdot 10^5, 1 \le d \le 10^9$) — lengden på tabellen og antallet spørringer.

Andre linje inneholder $n$ heltall $a_i$ ($0 \le a_i \le 10^9$) — beskrivelsen av tabellen.

De neste $q$ linjene inneholder et par heltall $[l_i, r_i]$ ($1 \le l_i \le r_i \le n$) — beskrivelsen av spørringene.

Utdata

Skriv ut $q$ heltall — svarene på spørringene.

Eksempler

Inndata 1

5 3 5
0 2 6 1 3
5 5
1 5
1 3

Utdata 1

2
2
3

Inndata 2

7 5 10
7 6 2 5 0 1 4
1 3
1 7
4 7
2 5
4 6

Utdata 2

3
2
3
3
4