Tienes la habilidad de crear robots cuya altura se encuentra en $[0, d]$. Para probarlos, construiste una línea de longitud $n$ que contiene algunos obstáculos. La descripción de los obstáculos se te da como un arreglo $a$. Si $a_i = 0$, entonces no hay ningún obstáculo en la $i$-ésima posición; de lo contrario, hay un obstáculo de altura $a_i > 0$.
Para probar tu robot, seleccionas un segmento $[l, r]$ y lo haces pasar por todos los obstáculos contenidos en el segmento. Cuando el robot encuentra un obstáculo con valor $a_i > 0$, ocurre una de las dos posibilidades siguientes:
- Si la altura actual del robot $h$ es menor que $a_i$, entonces no pasa nada ya que el robot es demasiado bajo para alcanzar el obstáculo.
- Si la altura actual del robot $h$ es al menos $a_i$, entonces la nueva altura cambia a $h' = h - a_i$.
Ahora debes responder $q$ consultas. Para cada uno de los $q$ segmentos $[l_i, r_i]$, debes indicar la máxima altura posible con la que puede terminar el robot después de atravesar los obstáculos del segmento si su altura inicial se eligió del intervalo $[0, d]$.
Entrada
La primera línea contiene los enteros $n, q, d$ ($1 \le n, q \le 3 \cdot 10^5, 1 \le d \le 10^9$) — la longitud del arreglo y el número de consultas.
La segunda línea contiene $n$ enteros $a_i$ ($0 \le a_i \le 10^9$) — la descripción del arreglo.
Las siguientes $q$ líneas contienen un par de enteros $[l_i, r_i]$ ($1 \le l_i \le r_i \le n$) — la descripción de las consultas.
Salida
Imprime $q$ enteros — las respuestas a las consultas.
Ejemplos
Entrada 1
5 3 5 0 2 6 1 3 5 5 1 5 1 3
Salida 1
2 2 3
Entrada 2
7 5 10 7 6 2 5 0 1 4 1 3 1 7 4 7 2 5 4 6
Salida 2
3 2 3 3 4