[XJTUPC 2024] Everyone's ALL IN

女士们，先生们。 早上好，中午好，以及晚上好。 欢迎来到“好得不能再好了！泰拉大师投资课”，我是你们的坎老师。 不要 10000，不要 5000，只需要 999 源石锭，一对一指导，手把手教学，从入门到精通，让你： ——**每选必赢，每投必中**，快速实现财富自由，富甲一方！ 今天我们来到的地点是——**卡西米尔骑士锦标赛**。 本次的赛事有点不同，首先， $N$ 位骑士将自行组成骑士团，其中第 $i$ 号骑士将进入第 $a_i$ 号骑士团； 然后接下来的 $M$ 天里，每天将指定两个不同的骑士团 $x$ 和 $y$ ，接下来每一位 $x$ 骑士团里的成员都和每一位 $y$ 骑士团里的成员进行一次比试。 我们每一次比试将会下注，如果两位骑士的编号分别为 $a$ 和 $b$，那么如果你下注成功了，你将获得你的本金和 $a\times b$ 的源石锭。 当然了，每次下注你需要压上你的**所有本金**！ 那么请问，接下来的 $M$ 天里，在我的指导下你每天分别可以获得多少源石锭？ **数据保证答案不超过 64 位有符号整型能表达的范围。** **赌博有风险，投资需谨慎！**  ## Input 输入第一行两个正整数 $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$ 中。 ## Output 输出共 $M$ 行，每行一个正整数，第 $i$ 行表示第 $i$ 天可以获得的最大收益。 **数据保证答案不超过 64 位有符号整型能表达的范围。** [samples] ## Note 骑士团 $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$。