题目描述

女士们，先生们。

早上好，中午好，以及晚上好。

欢迎来到“好得不能再好了！泰拉大师投资课”，我是你们的坎老师。

不要 10000，不要 5000，只需要 999 源石锭，一对一指导，手把手教学，从入门到精通，让你：

——每选必赢，每投必中，快速实现财富自由，富甲一方！

今天我们来到的地点是——卡西米尔骑士锦标赛。

本次的赛事有点不同，首先， $N$ 位骑士将自行组成骑士团，其中第 $i$ 号骑士将进入第 $a_i$ 号骑士团；

然后接下来的 $M$ 天里，每天将指定两个不同的骑士团 $x$ 和 $y$ ，接下来每一位 $x$ 骑士团里的成员都和每一位 $y$ 骑士团里的成员进行一次比试。

我们每一次比试将会下注，如果两位骑士的编号分别为 $a$ 和 $b$，那么如果你下注成功了，你将获得你的本金和 $a\times b$ 的源石锭。

当然了，每次下注你需要压上你的所有本金！

那么请问，接下来的 $M$ 天里，在我的指导下你每天分别可以获得多少源石锭？

数据保证答案不超过 64 位有符号整型能表达的范围。

赌博有风险，投资需谨慎！

输入格式

输入第一行两个正整数 $N$ ($1\le N \le 2\times 10^5$) 和 $M$ ($1\le M \le 2\times 10^5$)，由空格隔开。

接下来一行有 $N$ 个由空格隔开的正整数 $a_i$ ($1\le a_i \le 1\times 10^6$) ，表示编号为 $i$ 的骑士所在的骑士团的编号。

接下来 $M$ 行，每行两个由空格隔开的正整数 $x_i,y_i$ ($x_i \neq y_i$)，保证 $x_i,y_i$ 出现在 $a_1 \sim a_n$ 中。

输出格式

输出共 $M$ 行，每行一个正整数，第 $i$ 行表示第 $i$ 天可以获得的最大收益。

数据保证答案不超过 64 位有符号整型能表达的范围。

9 3
1 1 2 2 3 3 3 2 1
1 2
2 3
3 1

180
270
216

提示

骑士团 $1$ 的成员有 $\{1,2,9\}$，骑士团 $2$ 的成员有 $\{3,4,8\}$，骑士团 $3$ 的成员有 $\{5,6,7\}$。

第一天，骑士团 $1$ 和骑士团 $2$ 进行比赛。

获得的收益为：$1\times 3+1\times 4+1\times 8+2\times 3+2\times 4+2\times 8+9\times 3+9\times 4+9\times 8=180$。

第二天，骑士团 $2$ 和骑士团 $3$ 进行比赛。

获得的收益为：$3\times 5+3\times 6+3\times 7+4\times 5+4\times 6+4\times 7+8\times 5+8\times 6+8\times 7=270$。

第三天，骑士团 $1$ 和骑士团 $3$ 进行比赛。

获得的收益为：$1\times 5+1\times 6+1\times 7+2\times 5+2\times 6+2\times 7+9\times 5+9\times 6+9\times 7=216$。