You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

今天我们来到的地点是锦标赛的赛场｡ 本次的赛事有点不同，首先，$n$ 位选手将自行组成小组，其中第 $i$ 号选手将进入第 $a_i$ 个小组。 然后接下来的 $m$ 天里，每天将指定两个不同的小组 $x$ 和 $y$，接下来每一位 $x$ 小组里的成员都和每一位 $y$ 小组里的成员进行一次比试｡ 我们每一次比试将会下注，两位骑士的编号分别为 $a$ 和 $b$，那么如果你下注成功，你将获得你的本金和 $a \times b$ 的奖励｡ 当然了，如果你有本金，每次下注你需要压上你的所有本金！ 那么请问，接下来的 $m$ 天里，在每次都下注成功的前提下，你每天分别可以获得多少奖金？

请注意，你每天初始的本金是 $0$ , 但是你可以以 $0$ 元本金下注，只需要分别计算每天的利益即可。

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

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

输入格式：

第一行两个正整数 $n$ $(1 \le n \le 2 \cdot 10^5)$ 和 $m$ $(1 \le m \le 2 \cdot 10^5)$，由空格隔开｡ 接下来一行有 $n$ 个由空格隔开的正整数 $a_i$ $(1 \le a_i \le 10^6 )$，表示编号为 $i$ 的选手所在的小组的编号｡ 接下来 $M$ 行，每行两个由空格隔开的正整数 $x_i$ , $y_i$ ( $x_i$ ≠ $y_i$ )，保证 $x_i$ , $y_i$出现在 $a_1 ~ 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×3 + 1×4 + 1×8 + 2×3 + 2×4 + 2×8 + 9×3 + 9×3 + 9×8 = 180$｡

第二天，小组 $2$ 小组 $3$ 进行比赛

获得的收益为：

$3×5 + 3×6 + 3×7 + 4×5 + 4×6 + 4×7 + 8×5 + 8×6 + 8×7 = 270$｡

第三天，小组 1 和小组 3 进行比赛｡

获得的收益为：

$1×5 + 1×6 + 1×7 + 2×5 + 2×6 + 2×7 + 9×5 + 9×6 + 9×7 = 216$｡

限制与约定

对于 $40\%$的样例 ：

$1 \le n \le 100$ , $1 \le m \le 100$

对于 $100\%$ 的样例：

$1 \le n \le 2 \cdot 10^5$ , $1 \le m \le 2 \cdot 10^5$ $1 \le a_i \le 10^6$ $x_i$ ≠ $y_i$ ，保证 $x_i$ , $y_i$出现在 $a_1 ~ a_n$ 中｡

• 时间限制: $2 s$
• 空间限制: $256 MB$