Cho dãy số nguyên dương ~A = (a_0, a_1, \ldots, a_{n-1})~. Với một đoạn các phần tử liên tiếp ~a[L \ldots R]~ trong ~A~, người ta tính trọng số của nó theo cách sau:

Với mỗi số nguyên dương ~x~, gọi ~f(x)~ là số lần xuất hiện giá trị ~x~ trong đoạn ~a[L \ldots R]~. Khi đó trọng số của đoạn này được tính bằng

$$\sum_{x} f(x)^2 \cdot x$$

Bạn được cho ~q~ truy vấn, mỗi truy vấn ứng với một đoạn ~a[L \ldots R]~. Hãy cho biết trọng số của ~a[L \ldots R]~.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, q~ ~(n \le 10^5; q \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_0, a_1, \ldots, a_{n-1}~ ~(a_i \le 10^6)~.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~L, R~ ~(0 \le L \le R < n)~ ứng với một truy vấn.

Output

• Ứng với mỗi truy vấn, in ra trên một dòng trọng số tìm được.

Sample Input

8 2
1 1 2 2 1 3 1 1
0 5
1 6

Sample Output

20
20

Notes

• ~a[0 \ldots 5] = (1, 1, 2, 2, 1, 3)~;
• ~a[1 \ldots 6] = (1, 2, 2, 1, 3, 1)~.

Cả hai đoạn này đều có ~f(1) = 3~, ~f(2) = 2~, ~f(3) = 1~, nên trọng số bằng

$$3^2 \times 1 + 2^2 \times 2 + 1^2 \times 3 = 20$$