Sie haben die Fähigkeit, Roboter mit einer Höhe im Bereich $[0, d]$ zu bauen. Um sie zu testen, haben Sie eine Strecke der Länge $n$ mit einigen Hindernissen errichtet. Die Beschreibung der Hindernisse ist als Array $a$ gegeben. Wenn $a_i = 0$ ist, befindet sich an der $i$-ten Position kein Hindernis, andernfalls gibt es dort ein Hindernis der Höhe $a_i > 0$.
Um Ihren Roboter zu testen, wählen Sie ein Segment $[l, r]$ aus und lassen ihn alle in diesem Segment enthaltenen Hindernisse durchlaufen. Wenn der Roboter auf ein Hindernis mit dem Wert $a_i > 0$ trifft, tritt eine der beiden folgenden Möglichkeiten ein:
- Wenn die aktuelle Höhe $h$ des Roboters kleiner als $a_i$ ist, passiert nichts, da der Roboter zu klein ist, um das Hindernis zu berühren.
- Wenn die aktuelle Höhe $h$ des Roboters mindestens $a_i$ beträgt, ändert sich die neue Höhe zu $h' = h - a_i$.
Nun müssen Sie $q$ Anfragen beantworten. Für jedes der $q$ Segmente $[l_i, r_i]$ sollen Sie die größtmögliche Endhöhe bestimmen, die der Roboter nach dem Durchlaufen der Hindernisse im Segment haben kann, wenn seine Anfangshöhe aus dem Intervall $[0, d]$ gewählt wurde.
Eingabe
Die erste Zeile enthält die ganzen Zahlen $n, q, d$ ($1 \le n, q \le 3 \cdot 10^5, 1 \le d \le 10^9$) — die Länge des Arrays und die Anzahl der Anfragen.
Die zweite Zeile enthält $n$ ganze Zahlen $a_i$ ($0 \le a_i \le 10^9$) — die Beschreibung des Arrays.
Die nächsten $q$ Zeilen enthalten jeweils ein Paar ganzer Zahlen $[l_i, r_i]$ ($1 \le l_i \le r_i \le n$) — die Beschreibung der Anfragen.
Ausgabe
Geben Sie $q$ ganze Zahlen aus — die Antworten auf die Anfragen.
Beispiele
Eingabe 1
5 3 5 0 2 6 1 3 5 5 1 5 1 3
Ausgabe 1
2 2 3
Eingabe 2
7 5 10 7 6 2 5 0 1 4 1 3 1 7 4 7 2 5 4 6
Ausgabe 2
3 2 3 3 4