Dado un arreglo fijo de \(n\) enteros, responde \(q\) consultas: la suma de los elementos entre las posiciones \(i\) y \(j\), ambas incluidas.

Con \(10^5\) consultas sobre \(10^5\) elementos, sumar cada rango por separado es demasiado lento.

Entrada

La primera línea tiene \(n\) y \(q\) \((1 \le n, q \le 10^5)\). La segunda tiene el arreglo, con \(|a_i| \le 10^5\). Cada una de las siguientes \(q\) líneas tiene \(i\) y \(j\) \((0 \le i \le j < n)\).

Salida

Para cada consulta, una línea con la suma.

Ejemplo 1

Entrada

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

Salida

1
-1
-3