Sinulla on kyky luoda robotteja, joiden korkeus kuuluu välille $[0, d]$. Testataksesi niitä rakensit pituuden $n$ suoran radan, jolla on esteitä. Esteiden kuvaus annetaan taulukkona $a$. Jos $a_i = 0$, kohdassa $i$ ei ole estettä, ja muussa tapauksessa siinä on este, jonka korkeus on $a_i > 0$.
Testataksesi robottiasi valitset välin $[l, r]$ ja ajat robotin kaikkien kyseisellä välillä olevien esteiden läpi. Kun robotti kohtaa esteen, jonka arvo on $a_i > 0$, tapahtuu jompikumpi seuraavista:
- Jos robotin nykyinen korkeus $h$ on pienempi kuin $a_i$, mitään ei tapahdu, sillä robotti on liian matala osumaan esteeseen.
- Jos robotin nykyinen korkeus $h$ on vähintään $a_i$, uudeksi korkeudeksi muuttuu $h' = h - a_i$.
Nyt sinun tulee vastata $q$ kyselyyn. Jokaiselle $q$ välistä $[l_i, r_i]$ sinun tulee ilmoittaa suurin mahdollinen korkeus, joka robotilla voi olla sen kuljettua välin esteiden läpi, kun alkukorkeus valitaan väliltä $[0, d]$.
Syöte
Ensimmäinen rivi sisältää kokonaisluvut $n, q, d$ ($1 \le n, q \le 3 \cdot 10^5, 1 \le d \le 10^9$) — taulukon pituuden ja kyselyiden lukumäärän.
Toinen rivi sisältää $n$ kokonaislukua $a_i$ ($0 \le a_i \le 10^9$) — taulukon kuvauksen.
Seuraavat $q$ riviä sisältävät kokonaislukuparin $[l_i, r_i]$ ($1 \le l_i \le r_i \le n$) — kyselyiden kuvauksen.
Tuloste
Tulosta $q$ kokonaislukua — vastaukset kyselyihin.
Esimerkit
Syöte 1
5 3 5 0 2 6 1 3 5 5 1 5 1 3
Tuloste 1
2 2 3
Syöte 2
7 5 10 7 6 2 5 0 1 4 1 3 1 7 4 7 2 5 4 6
Tuloste 2
3 2 3 3 4