Dado un arreglo de ~n~ enteros, su tarea es procesar ~q~ consultas de la forma: ¿cuál es la suma de los valores en el rango ~[a,b]~?

Entrada

• La primera línea de entrada contiene dos enteros, ~n~ y ~q~: el número de valores y consultas.
• La segunda línea contiene ~n~ enteros ~x_1,x_2,\cdots,x_n~: los valores del arreglo.
• Finalmente, hay ~q~ líneas que describen las consultas. Cada línea contiene dos enteros, ~a~ y ~b~: ¿cuál es la suma de los valores en el rango ~[a,b]~?

Salida

Imprima el resultado de cada consulta.

Restricciones

• ~1 \leq n,q \leq 2 \cdot 10^5~
• ~1 \leq x_i \leq 10^9~
• ~1 \leq a \leq b \leq n~

Ejemplo de Entrada

8 4
3 2 4 5 1 1 5 3
2 4
5 6
1 8
3 3

Ejemplo de Salida

11
2
24
4