题目描述

给定一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$。有 $q$ 次查询操作，每次查询操作会给你两个整数 $l$ 和 $r$，你需要回答出区间 $[l, r]$ 范围内所有出现过的数值与它出现次数的平方的乘积之和（举个例子，如果这个数值为 $s$，而 $K_s$ 对应区间 $[l, r]$ 范围内等于 $s$ 的元素个数，则你需要求的是 $s \times K_s \times K_s$）之和，即 $\sum\limits_s s \times K_s^2$。

举个例子，如果查询的区间范围内有 $3$ 个数值为 $2$ 的数，$5$ 个数值为 $3$ 的数，则对应的查询结果为 $2 \times 3^2 + 3 \times 5^2 = 93$。

输入格式

第一行，两个整数 $n$ 和 $q$（$1 \le n,q \le 2 \times 10^5$），分别表述出列长度及查询次数。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(1 \le a_i \le 10^6)$。

接下来 $q$ 行，每行包含两个整数 $l$ 和 $r$（$1 \le l \le r \le n$），表示一次查询。

输出格式

输出共 $q$ 行，每行包含一个整数，表示查询的结果。

样例

8 3
1 1 2 1 2 3 2 2
1 3
2 5
2 8

6
12
39

说明/提示

样例解释

• 对于第 $1$ 次询问的区间 $[1,3]$：$1$ 出现了 $2$ 次，$2$ 出现了 $1$ 次，对应的查询结果为 $1 \times 2^2 + 2 \times 1^2 = 6$；
• 对于第 $2$ 次询问的区间 $[2,5]$：$1$ 出现了 $2$ 次，$2$ 出现了 $2$ 次，对应的查询结果为 $1 \times 2^2 + 2 \times 2^2 = 12$；
• 对于第 $3$ 次询问的区间 $[2,8]$：$1$ 出现了 $2$ 次，$2$ 出现了 $4$ 次，$3$ 出现了 $1$ 次，对应的查询结果为 $1 \times 2^2 + 2 \times 4^4 + 3 \times 1^2 = 39$。

数据规模与约定

• 对于 $30\%$ 的数据，$n, q \le 20$
• 对于 $60\%$ 的数据，$n, q \le 2000$
• 对于 $100\%$ 的数据，$1 \le n, q \le 2 \times 10^5, 1 \le a_i \le 10^6$