给出一个正整数数组 a1, a2, ..., an。让我们考虑它的任意子数组 al, al + 1..., ar,其中 1 ≤ l ≤ r ≤ n。对于每个正整数 s,Ks 表示 s 在子数组中出现的次数。我们将子数组的幂称为每个正整数 s 的乘积之和 Ks·Ks·s。总和仅包含有限数量的非零被加数,因为数组中不同值的数量确实是有限的。
您应该计算给定子数组 t 的幂。
输入
第一行包含两个整数 n 和 t (1 ≤ n, t ≤ 200000) — 对应的数组长度和查询次数。
第二行包含 n 个正整数 ai (1 ≤ ai ≤ 106) — 数组的元素。
接下来 t 行包含两个正整数 l, r (1 ≤ l ≤ r ≤ n) - 相应子数组左端和右端的索引。
输出
输出 t 行,输出的第 i 行应包含单个正整数 - 第 i 个查询子数组的幂。
请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cout 流(也可以使用 %I64d)。
示例
输入 #1
3 2 1 2 1 1 2 1 3
输出 #1
3 6
输入 #2
8 3 1 1 2 2 1 3 1 1 2 7 1 6 2 7
输出 #2
20 20 20
注意
考虑以下数组(请参阅第二个示例)及其 [2, 7] 子数组(子数组的元素已着色):