Cho dãy ~a~ gồm ~n~ phần tử ~a_1, a_2, ..., a_n~. Gọi ~a[l..r]~ là đoạn con có các phần tử ở vị trí từ ~l~ đến ~r \ (1 \le l \le r \le n)~.

Gọi ~f(x, l, r)~ là số lần xuất hiện của phần tử có giá trị là ~x~ trong đoạn ~a[l..r]~. Gọi ~S(l, r)~ là tập hợp các phần tử phân biệt có trong đoạn ~a[l..r]~.

Cho ~q~ truy vấn, mỗi truy vấn gồm hai số nguyên dương ~l_i, r_i \ (1 \le i \le q)~. Hãy tính giá trị của: $$P(l_i, r_i) = \displaystyle{\sum_{x \in S(l_i, r_i)} (f(x, l_i, r_i) \times f(x, l_i, r_i) \times x)}.$$

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, q;~
• Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, ..., a_n \ (1 \le a_i \le 10^6, \ 1 \le i \le n);~
• ~q~ dòng sau, mỗi dòng chứa hai số nguyên ~l_i, r_i \ (1 \le l_i \le r_i \le n, \ 1 \le i \le q).~

Output

In ra ~q~ dòng, dòng thứ ~i \ (1 \le i \le q)~ là kết quả của ~P(l_i, r_i)~.

Scoring

• Subtask 1 [40%]: ~n, q \le 1000;~
• Subtask 2 [60%]: ~n, q \le 10^5~.

Examples

Input

3 2 
1 2 1 
1 2 
1 3

Output

3
6

Giải thích:

• ~P(1, 2) = (1 \times 1 \times 1) + (1 \times 1 \times 2) = 3;~
• ~P(1, 3) = (2 \times 2 \times 1) + (1 \times 1 \times 2) = 6.~