Descripción

Tienes un arreglo de \(N\) números enteros. Ahora se realizarán \(Q\) consultas.

Cada consulta es de la forma:

Suma de los elementos en las posiciones \([L, R]\)

Es decir, para cada consulta con dos enteros \(L\) y \(R\), debes calcular la suma de los elementos del arreglo entre las posiciones \(L\) y \(R\), inclusive, donde se cumple \(1 \leq L \leq R \leq N\).

Entrada

La entrada consiste en un solo caso de prueba con el siguiente formato:

En la primera línea, dos enteros \(N\) y \(Q\) \((1 \leq N \leq 10^6, 1 \leq Q \leq 10^6)\) — el tamaño del arreglo y el número de consultas. En la segunda línea, \(N\) enteros \(a_1, a_2, \ldots, a_N\) \((1 \leq a_i \leq 10^9)\) — los elementos del arreglo. En cada una de las siguientes \(Q\) líneas, dos enteros \(L\) y \(R\) \((1 \leq L \leq R \leq N)\) — los límites izquierdo y derecho de la consulta.

Todas las posiciones están indexadas desde 1.

Salida

Imprimir \(Q\) líneas. En la \(i\)-ésima línea, imprimir un solo número entero: la suma de los elementos desde la posición \(L\) hasta la posición \(R\) de la \(i\)-ésima consulta (incluidas).

Ejemplos

Entrada

5 3 
1 2 3 4 5 
1 3 
2 5 
4 4

Salida

6 
14 
4

Entrada

4 2 
1000000000 1000000000 1 2 
1 1 
1 2

Salida

1000000000 
2000000000