Du har förmågan att skapa robotar med en höjd i intervallet $[0, d]$. För att testa dem har du byggt en bana av längd $n$ som innehåller några hinder. Beskrivningen av hindren ges som en array $a$. Om $a_i = 0$ finns det inget hinder på den $i$-te positionen, och annars finns det ett hinder med höjden $a_i > 0$.

För att testa din robot väljer du ett segment $[l, r]$ och låter den köra igenom alla hinder som finns i segmentet. När roboten stöter på ett hinder med värdet $a_i > 0$ inträffar ett av följande två fall:

• Om robotens nuvarande höjd $h$ är mindre än $a_i$ händer ingenting eftersom roboten är för kort för att nå upp till hindret.
• Om robotens nuvarande höjd $h$ är minst $a_i$ ändras den nya höjden till $h' = h - a_i$.

Nu behöver du besvara $q$ frågor. För vart och ett av de $q$ segmenten $[l_i, r_i]$ ska du ange den maximalt möjliga höjd som roboten kan sluta med efter att ha kört igenom hindren i segmentet om starthöjden valdes från intervallet $[0, d]$.

Indata

Första raden innehåller heltalen $n, q, d$ ($1 \le n, q \le 3 \cdot 10^5, 1 \le d \le 10^9$) — arrayens längd och antalet frågor.

Andra raden innehåller $n$ heltal $a_i$ ($0 \le a_i \le 10^9$) — beskrivningen av arrayen.

Följande $q$ rader innehåller ett par heltal $[l_i, r_i]$ ($1 \le l_i \le r_i \le n$) — beskrivningen av frågorna.

Utdata

Skriv ut $q$ heltal — svaren på frågorna.

Exempel

Indata 1

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

Utdata 1

2
2
3

Indata 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