Þú hefur getu til að búa til vélmenni sem hafa hæð á bilinu $[0, d]$. Til að prófa þau smíðaðir þú braut af lengd $n$ sem inniheldur nokkrar hindranir. Lýsingin á hindrununum er gefin sem fylki $a$. Ef $a_i = 0$ þá er engin hindrun í $i$-ta sæti, en annars er þar hindrun af hæð $a_i > 0$.

Til að prófa vélmennið þitt velur þú bil $[l, r]$ og lætur það fara í gegnum allar hindranir sem eru á bilinu. Þegar vélmennið mætir hindrun með gildi $a_i > 0$ gerist annað af tvennu:

• Ef núverandi hæð vélmennisins $h$ er minni en $a_i$, þá gerist ekkert þar sem vélmennið er of lágt til að rekast í hindrunina.
• Ef núverandi hæð vélmennisins $h$ er að minnsta kosti $a_i$, þá breytist nýja hæðin í $h' = h - a_i$.

Nú þarftu að svara $q$ fyrirspurnum. Fyrir hvert af $q$ bilunum $[l_i, r_i]$ þarftu að segja til um hver mesta mögulega hæðin er sem vélmennið getur endað með eftir að hafa farið í gegnum hindranirnar á bilinu ef upphafshæðin var valin af bilinu $[0, d]$.

Inntak

Fyrsta línan inniheldur heiltölurnar $n, q, d$ ($1 \le n, q \le 3 \cdot 10^5, 1 \le d \le 10^9$) — lengd fylkisins og fjölda fyrirspurna.

Önnur línan inniheldur $n$ heiltölur $a_i$ ($0 \le a_i \le 10^9$) — lýsingu á fylkinu.

Næstu $q$ línur innihalda tvennd heiltalna $[l_i, r_i]$ ($1 \le l_i \le r_i \le n$) — lýsingu á fyrirspurnunum.

Úttak

Skrifið út $q$ heiltölur — svörin við fyrirspurnunum.

Dæmi

Inntak 1

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

Úttak 1

2
2
3

Inntak 2

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

Úttak 2

3
2
3
3
4