← 返回题目列表

Codeforces · 86/D

D. 强大的阵列

中文机器翻译题面 查看原题

给出一个正整数数组 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] 子数组(子数组的元素已着色):