Module: Algoritmo Mo

Problem

Hay una matriz de números naturales a₁, a₂, ..., a_n. Considere algunos de sus subarreglos a_l, a_l + 1, ..., a_r, donde 1 ≤ l ≤ r ≤ n, y para cada número natural s denote por K_s el número de ocurrencias del número s en este subarreglo. Llamemos cardinalidad de un subarreglo a la suma de los productos K_s·K_s·s sobre todos los enteros distintos s. Dado que la cantidad de números diferentes en la matriz es finita, la suma contiene solo una cantidad finita de términos distintos de cero.

Es necesario calcular las cardinalidades de cada uno de los t subarreglos dados.

Entrada
La primera línea contiene dos números enteros n y t (1 ≤ n, t ≤ 200000) — la longitud de la matriz y el número de solicitudes, respectivamente.
La segunda línea contiene n números naturales ai (1 ≤ a_i ≤ 10⁶) — elementos de matriz.
Las siguientes líneas t contienen dos enteros positivos l y r (1 ≤ l ≤ r ≤ n) — índices de los extremos izquierdo y derecho del subarreglo correspondiente.

Impresión
Imprime t líneas, donde la i-ésima línea contiene el único número natural — cardinalidad del i-ésimo subarreglo de consulta.

Ejemplos:
 

Entrada	Salida
3 2 1 2 1 1 2 1 3	3 6
8 3 1 1 2 2 1 3 1 1 27 16 27	20 20 20