说明

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

Nogonia 是一个规划城市，拥有 $N$ 个路口，编号从 $1$ 到 $N$，以及 $M$ 条街道。每条街道双向连接两个路口。保证任意路口都可以通过街道到达所有其他路口，且任意两个路口之间最多由一条街道直接相连。

Nogonia 市政$$府为每个路口 $i$ 公布了一个 危险评级 $D_i$。然而，Alice 认为这些评级还不够，因为她想评估在城市中移动的安全性，而不仅仅是她居住的地点。因此，她开发了自己的方法来衡量这座城市的危险程度。

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

换句话说，一个路口 $U$ 的危险分数是它与城市中每一个路口之间的风险因子之和。

为所有路口计算这些危险分数并不容易，所以 Alice 请求你的帮助！

输入格式

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

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

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

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

输出格式

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

3 2
1 3 1
1 2
2 3

7 9 7

3 3
1 3 1
2 3
1 2
3 1

5 9 5

提示

翻译由 DeepSeek V3 完成