Tết mới hết nhưng xuân mới về. Loli sau những ngày lao động mồm mép vất vả, cuối cùng mới tích cóp được vài… nghìn tiền mừng tuổi để simp gái 2D. Tiền mừng tuổi với Loli như là một báu vật, được Loli cất giấu trong một cái hộp (để tránh bị mẹ nổi hứng "cầm hộ").

Loli đặt số thứ tự và phân loại cho từng lì xì một, đánh số từ ~1~ tới ~N~. Hắn định nghĩa một xấp lì xì con ~(i,j)~ bao gồm lì xì thứ ~i, i+1, \dots,j~. Với mỗi loại lì xì ~S~, ta đặt ~K_S~ là số lì xì loại ~S~ xuất hiện trong xấp lì xì con ~(i,j)~. Ta định nghĩa giá trị của xấp lì xì con ~(i,j)~ là tổng:

~ \sum_{S \in \mathbb{N}} K_S \times S ~

Công việc của bạn khá đơn giản: Bạn được cho biết trước dãy lì xì ban đầu, hãy trả lời ~M~ truy vấn, mỗi truy vấn có dạng hai số nguyên ~L~, ~R~ ~(1 \le L \le R \le N)~ với yêu cầu tính giá trị của xấp lì xì con ~(L,R)~.

Input:

• Dòng đầu tiên chứa hai số nguyên ~N, M~ ~(1 \le N, M \le 10^5)~ – số lì xì và số truy vấn.
• Dòng thứ ~2~ cho ~N~ số nguyên ~a_i~ ~(1 \le a_i \le 10^9)~ – loại của lì xì thứ ~i~.
• ~M~ dòng tiếp theo: Dòng ~i~ chứa 2 số nguyên ~L_i, R_i~ ~(1 \le L_i \le R_i ≤ N)~ mô tả truy vấn thứ ~i~.

Output:

• Gồm ~M~ dòng, mỗi dòng in ra kết quả thỏa mãn đề bài.

Sample Input

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

Sample Output

5
10

Giải thích

• Truy vấn đầu tiên, có 2 lì xì loại 1, 1 lì xì loại 3, vậy kết quả là ~2 \times 1 + 1 \times 3 = 5~.
• Truy vấn thứ hai, có 3 lì xì loại 1, 2 lì xì loại 2, 1 lì xì loại 3, kết quả là ~3 \times 1 + 2 \times 2 + 1 \times 3 = 10~.