Sức mạnh đoạn con

Cho mảng gồm $n$ số nguyên dương $a_1,a_2,\dots ,a_n$. Xét một đoạn con $a_l,a_{l+1},\dots ,a_r$ với $1\le l\le r\le n$. Với mỗi số nguyên dương $s$, gọi $K_s$ là số lần xuất hiện của $s$ trong đoạn con đó. Sức mạnh của đoạn con được định nghĩa là tổng $K_s·K_s·s$ trên mọi số nguyên dương $s$ (tổng này chỉ có hữu hạn số hạng khác $0$).

Cho $t$ truy vấn, mỗi truy vấn gồm hai chỉ số $l,r$. Hãy tính sức mạnh của đoạn con tương ứng với từng truy vấn.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $t$: độ dài mảng và số truy vấn.
• Dòng thứ hai chứa $n$ số nguyên dương $a_1,a_2,\dots ,a_n$.
• $t$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l,r$ ($1\le l\le r\le n$): hai đầu mút của đoạn con.

Dữ liệu ra

In ra $t$ dòng, dòng thứ $i$ chứa một số nguyên dương duy nhất: sức mạnh của đoạn con trong truy vấn thứ $i$.

Ràng buộc

• $1\le n,t\le 2·{10}^5$
• $1\le a_i\le {10}^6$

Ví dụ