Cho dãy số nguyên dương ~a_1, a_2, \dots, a_n~. Với mỗi dãy con ~a_l, a_{l+1}, \dots, a_r~ (~1 \le l \le r \le n~) ta định nghĩa giá trị của dãy là biểu thức: ~\sum_{s \in \mathbb{N}} K_s^2 \cdot s~ Trong đó ~K_s~ là số lần xuất hiện của ~s~ trong dãy con ~a_l, a_{l+1}, \dots, a_r~.

Ví dụ, dãy con ~[2, 7]~ của dãy: ~[1, 1, 2, 2, 1, 3, 1, 1]~ có ~K_1 = 3, K_2 = 2, K_3 = 1~ các giá trị khác bằng 0, do vậy giá trị của nó là ~3^2 \cdot 1 + 2^2 \cdot 2 + 1^2 \cdot 3 = 20~.

Yêu cầu: Cho ~t~ dãy con, hãy xác định giá trị của mỗi dãy.

Input

• Dòng 1: Chứa hai số nguyên ~n, t~ (~1 \le n, t \le 2 \times 10^5~).
• Dòng 2: Chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^6~).
• Dòng 3, 4, \dots, t + 2: Dòng thứ ~k + 2~ chứa hai số nguyên ~l, r~ (~1 \le l \le r \le n~) mô tả dãy con thứ ~k~ (~k = 1, 2, \dots, t~).

Output

• Gồm ~t~ dòng, dòng thứ ~k~ ghi một số nguyên là giá trị của dãy con thứ ~k~ (~k = 1, 2, \dots, t~).

Sample Input 1

3 2
1 2 1
1 2
1 3

Sample Output 1

3
6