Su tarea consiste en mantener un arreglo de ~n~ valores y procesar eficientemente los siguientes tipos de consultas:

1. Aumentar el primer valor del rango ~[a,b]~ en ~1~, el segundo en ~2~, el tercero en ~3~, y así sucesivamente.
2. Calcular la suma de los valores del rango ~[a,b]~.

Entrada

• La primera línea de entrada contiene dos enteros ~n~ y ~q~: el tamaño del arreglo y el número de consultas.
• La siguiente línea contiene n valores ~t_1,t_2,\dots,t_n~: el contenido inicial del arreglo.
• Finalmente, hay ~q~ líneas que describen las consultas. El formato de cada línea es "~1~ ~a~ ~b~" o "~2~ ~a~ ~b~".

Salida

Imprimir la respuesta a cada consulta de suma.

Restricciones

• ~1 \leq n, q \leq 2 \cdot 10^5~
• ~1 \leq t_i \leq 10^6~
• ~1 \leq a \leq b \leq n~

Ejemplo de Entrada

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

Ejemplo de Salida

17
32