Cho mảng \(A\) gồm \(N\) số nguyên dương. Có \(Q\) truy vấn, mỗi truy vấn gồm hai số nguyên \(L, R\). Với mỗi truy vấn, hãy tính sức mạnh của đoạn con \(A[L \ldots R]\).

Sức mạnh của đoạn con \([L, R]\) được xác định bởi công thức:

\[ \operatorname{Power}(L,R)=\sum_x cnt[x]^2 \cdot x \]

Trong đó, \(cnt[x]\) là số lần xuất hiện của giá trị \(x\) trong đoạn \(A[L \ldots R]\). Tổng được tính trên tất cả các giá trị \(x\) xuất hiện trong đoạn.

Input

• Dòng đầu tiên chứa hai số nguyên \(N, Q\).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A1, A2, \ldots, A_N\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L, R\), mô tả một truy vấn.

Output

In ra \(Q\) dòng, dòng thứ \(i\) chứa sức mạnh của đoạn con tương ứng với truy vấn thứ \(i\).

Constraints

• \(1 \le N, Q \le 10^6\).
• \(1 \le A_i \le 10^6\).
• \(1 \le L \le R \le N\).

Time limit: \(1.5\) seconds.