Hai la capacità di creare robot di altezza compresa in $[0, d]$. Per testarli, hai costruito un percorso lineare di lunghezza $n$ contenente alcuni ostacoli. La descrizione degli ostacoli ti viene fornita come un array $a$. Se $a_i = 0$, allora non c'è alcun ostacolo nella $i$-esima posizione; altrimenti, c'è un ostacolo di altezza $a_i > 0$.
Per testare il tuo robot, selezioni un segmento $[l, r]$ e lo fai correre attraverso tutti gli ostacoli contenuti nel segmento. Quando il robot incontra un ostacolo con valore $a_i > 0$, si verifica una delle due possibilità:
- Se l'altezza attuale del robot $h$ è minore di $a_i$, allora non succede nulla poiché il robot è troppo basso per raggiungere l'ostacolo.
- Se l'altezza attuale del robot $h$ è almeno $a_i$, allora la nuova altezza diventa $h' = h - a_i$.
Ora devi rispondere a $q$ query. Per ciascuno dei $q$ segmenti $[l_i, r_i]$, devi determinare la massima altezza possibile con cui il robot può terminare il percorso dopo aver attraversato gli ostacoli nel segmento, scegliendo l'altezza iniziale nell'intervallo $[0, d]$.
Input
La prima riga contiene gli interi $n, q, d$ ($1 \le n, q \le 3 \cdot 10^5, 1 \le d \le 10^9$) — la lunghezza dell'array e il numero di query.
La seconda riga contiene $n$ interi $a_i$ ($0 \le a_i \le 10^9$) — la descrizione dell'array.
Le successive $q$ righe contengono una coppia di interi $[l_i, r_i]$ ($1 \le l_i \le r_i \le n$) — la descrizione delle query.
Output
Stampa $q$ interi — le risposte alle query.
Esempi
Input 1
5 3 5 0 2 6 1 3 5 5 1 5 1 3
Output 1
2 2 3
Input 2
7 5 10 7 6 2 5 0 1 4 1 3 1 7 4 7 2 5 4 6
Output 2
3 2 3 3 4