给定一个数组a1~an，现在给出t个询问，每一个询问给出l,r两数，定义在l~r子数组中s这个数出现的次数为x(s)，则对于l~r子数组中出现的每一个数s，求x*x*s的和。 An array of positive integers a1,a2,...,an is given. Let us consider its arbitrary subarray al,al+1...,ar,where 1<=l<=r<=n. For every positive integer s denote by Ks the number of occurrences of s into the subarray. We call the power of the subarray the sum of products Ks*Ks*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.

First line contains two integers n and t (1<=n,t<=50000) — the array length and the number of queries correspondingly. Second line contains n positive integers ai (1<=ai<=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. 第一行包含两个整数n和t(1 <= n，t <= 50000)-数组长度和查询数量。 第二行包含n个正整数ai(1 <= ai <= 10^6)- 数组的元素。 接下来的t行包含两个正整数l，r(1<=l<=r<= n)。

Output t lines, the i-th line of the output should contain single positive integer — the power of the i-th query subarray. 输出t行，输出的第i行应该包含单个正整数 - 第i个查询子阵列的答案。

#第一组样例
3 2
1 2 1
1 2
1 3

#第二组样例
8 3
1 1 2 2 1 3 1 1
2 7
1 6
2 7

#第一组样例
3
6

#第二组样例
20
20
20