Descripción

La duración de la maniobra le dio a Renata Quijada el radio de búsqueda, y la pista de aterrizaje apareció a las afueras de Hidalgo del Parral. Ahí el rastro cambió de forma: quien se llevó el meteorito necesitaba dinero en efectivo, y en Parral eso significa la casa de empeño La Fortuna.

El encargado no suelta nombres, pero sí deja consultar el libro de operaciones del mes. En el libro hay ~N~ piezas empeñadas; la ~i~-ésima se empeñó en ~p_i~ pesos.

A Renata no le sirve el libro completo: lo que busca es el rango de precios en el que se movió el ladrón, y para acorralarlo va a hacer ~Q~ preguntas. Todas sus preguntas son de alguno de estos dos tipos, y siempre se refieren a un rango de precios ~[L, R]~:

• Tipo 1: ¿cuántas piezas se empeñaron entre ~L~ y ~R~ pesos.
• Tipo 2: ¿cuánto dinero en total se pagó por las piezas que se empeñaron entre ~L~ y ~R~ pesos.

El encargado tiene poca paciencia y Renata necesita las respuestas de inmediato[. Ayúdale a contestarlas todas.

Entrada

La primera línea contiene dos enteros ~N~ y ~Q~: la cantidad de piezas del libro y la cantidad de preguntas.

La segunda línea contiene ~N~ enteros separados por espacios: ~p_1, p_2, \ldots, p_N~.

Cada una de las siguientes ~Q~ líneas contiene tres enteros ~t~, ~L~ y ~R~, que describen una pregunta del tipo ~t~ sobre el rango de precios ~[L, R]~.

Salida

Imprime ~Q~ líneas, una por cada pregunta, en el mismo orden en que aparecen en la entrada, con la respuesta correspondiente. Si ninguna pieza cae en el rango, la respuesta es 0 en ambos tipos de pregunta.

Ejemplos

Ejemplo 1

Entrada

6 4

5 3 5 10 1 3

1 3 5

2 3 5

1 6 100

2 1 10

Salida

4

16

1

27

Explicación Las piezas empeñadas entre ~3~ y ~5~ pesos son 5, 3, 5 y 3: son ~4~ piezas (primera pregunta) por las que se pagaron ~5+3+5+3 = 16~ pesos (segunda pregunta).

En el rango ~[6, 100]~ sólo cae la pieza de ~10~ pesos.

En el rango ~[1, 10]~ caen todas, y el total pagado en el mes fue de ~27~ pesos.

Ejemplo 2

Entrada

3 3

1000000 1000000 1000000

2 1 1000000

1 1 999999

2 500000 500000

Salida

3000000

0

0

Explicación Las tres piezas se empeñaron al precio máximo posible. La primera pregunta suma las tres. En las otras dos no cae ninguna pieza dentro del rango, así que la respuesta es ~0~.

Límites

• ~1 \le N \le 500\,000~
• ~1 \le Q \le 300\,000~
• ~1 \le p_i \le 1\,000\,000~
• ~t \in \{1, 2\}~
• ~1 \le L \le R \le 1\,000\,000~

La entrada y la salida de este problema son grandes: conviene usar scanf/printf, o bien cin/cout con ios_base::sync_with_stdio(false); cin.tie(NULL);.

Subtareas

Grupo	Puntos	Restricciones adicionales
1	20	~N \le 1\,000~ y ~Q \le 1\,000~
2	20	Todas las preguntas son de tipo 1
3	30	~N \le 100\,000~ y ~Q \le 100\,000~
4	30	Sin restricciones adicionales