Đề bài

Cho dãy ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~. Một dãy con ~(l, r)~ là dãy ~a_l, a_{l+1}, \dots, a_r~ (~1 \leq l \leq r \leq n~).

Với mỗi số nguyên dương ~s~, đặt ~K_s~ là số lần ~s~ xuất hiện trong dãy con ~(l, r)~. Ta định nghĩa giá trị của dãy con ~(l, r)~ là tổng:

~\sum_{s \in \mathbb{N}} K_s^2 \cdot s~

Yêu cầu: Cho biết trước dãy ~a_1, a_2, \dots, a_n~. Hãy trả lời ~m~ truy vấn, mỗi truy vấn có dạng hai số nguyên ~L, R~ (~1 \leq L \leq R \leq n~) với yêu cầu tính giá trị của dãy con ~a_L, a_{L+1}, \dots, a_R~.

Input

• Dòng 1: Chứa hai số nguyên dương ~n, m~ (~1 \leq n, m \leq 2 \cdot 10^5~).
• Dòng 2: Chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \leq a_i \leq 10^9~).
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~L_i, R_i~ (~1 \leq L_i, R_i \leq n~) mô tả truy vấn thứ ~i~.

Output

• In ra ~m~ dòng, mỗi dòng một số nguyên là kết quả của một truy vấn (theo thứ tự xuất hiện trong input).

Ví dụ

Sample Input 1

3 2
1 2 1
1 2
1 3

Sample Output 1

3
6

Sample Input 2

8 3
1 1 2 2 1 3 1 1
2 7
1 6
2 7

Sample Output 2

20
20
20

Giới hạn

• Thời gian: 1.0s
• Bộ nhớ: 256M