Alice 准备搬到 Nlogonia 市，为了决定住在哪里，她正在评估这座城市的安全性。

Nlogonia 是一座规划城市，拥有 $N$ 个交叉路口（编号从 1 到 $N$）和 $M$ 条街道。每条街道双向连接两个交叉路口。保证任意两个交叉路口之间都可以通过街道到达，且没有两条街道连接同一对交叉路口。

Nlogonia 政府为每个交叉路口 $i$ 发布了一个危险等级 $D_i$。然而，Alice 认为这些等级不足以评估城市的安全性，因为她想评估的是在城市中穿行的安全性，而不仅仅是她居住地点的安全性。因此，她开发了自己的方法来衡量这座城市有多危险。

对于城市中的任意路径，Alice 将其“路径风险”定义为该路径上所有交叉路口（包括端点）中危险等级的最大值。两个交叉路口 $U$ 和 $V$ 之间的“风险因子”，记作 $f(U, V)$，定义为连接 $U$ 和 $V$ 的所有路径中，路径风险的最小值。根据定义，从交叉路口 $U$ 到其自身的唯一路径是仅包含 $U$ 的平凡路径，因此我们有 $f(U, U) = D_U$。最后，她为每个交叉路口 $U$ 分配了一个“危险得分”，记作：

$$S_U = \sum_{V=1}^{N} f(U, V)$$

换句话说，一个交叉路口 $U$ 的危险得分是它到城市中每个交叉路口的风险因子之和。

计算所有交叉路口的这些危险得分并不容易，所以 Alice 向你寻求帮助！

输入格式

第一行包含两个整数 $N$ ($2 \le N \le 3 \cdot 10^5$) 和 $M$ ($1 \le M \le 3 \cdot 10^5$)，分别表示 Nlogonia 的交叉路口数量和街道数量。每个交叉路口由 1 到 $N$ 之间的一个不同整数标识。

第二行包含 $N$ 个整数 $D_1, D_2, \dots, D_N$ ($1 \le D_i \le 10^9$，对于 $i = 1, 2, \dots, N$)，其中 $D_i$ 是交叉路口 $i$ 的危险等级。

接下来的 $M$ 行，每行包含两个整数 $U$ 和 $V$ ($1 \le U, V \le N$ 且 $U \neq V$)，表示交叉路口 $U$ 和 $V$ 之间有一条双向街道。

保证每对交叉路口之间最多只有一条街道，且任意交叉路口都可以通过一条或多条街道到达其他任何交叉路口。

输出格式

输出一行，包含 $N$ 个整数 $S_1, S_2, \dots, S_N$，即所有交叉路口的危险得分。

样例

输入 1

3 2
1 3 1
1 2
2 3

输出 1

7 9 7

输入 2

3 3
1 3 1
2 3
1 2
3 1

输出 2

5 9 5