An array of positive integers $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$ is given. Let us consider its arbitrary subarray $*a*_{*l*}, *a*_{*l* + 1}..., *a*_{*r*}$, where $1 ≤ *l* ≤ *r* ≤ *n*$. For every positive integer $*s*$ denote by $*K*_{*s*}$ the number of occurrences of $*s*$ into the subarray. We call the power of the subarray the sum of products $*K*_{*s*}·*K*_{*s*}·*s*$ for every positive integer $*s*$. The sum contains only finite number of nonzero summands as the number of different values in the array is indeed finite.

You should calculate the power of $*t*$ given subarrays.

Input

First line contains two integers $*n*$ and $*t*$ ($1 ≤ *n*, *t* ≤ 200000$) — the array length and the number of queries correspondingly.

Second line contains $*n*$ positive integers $*a*_{*i*}$ ($1 ≤ *a*_{*i*} ≤ 10^{6}$) — the elements of the array.

Next $*t*$ lines contain two positive integers $*l*$, $*r*$ ($1 ≤ *l* ≤ *r* ≤ *n*$) each — the indices of the left and the right ends of the corresponding subarray.

Output

Output $*t*$ lines, the $*i*$-th line of the output should contain single positive integer — the power of the $*i*$-th query subarray.

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preferred to use cout stream (also you may use %I64d).

Note

Consider the following array (see the second sample) and its [2, 7] subarray (elements of the subarray are colored):

Then

K₁ = 3

,

K₂ = 2

,

K₃ = 1

, so the power is equal to

3²·1 + 2²·2 + 1²·3 = 20

.