雅加达有 $N$ 个路口（编号从 $1$ 到 $N$），由 $M$ 条双向道路连接，使得从任何一个路口出发，经过一条或多条道路都能到达其他任何路口。第 $i$ 个路口的高度为 $H_i$。

Ahmad 热爱骑行，尤其喜欢平坦的道路。他认为如果道路是上坡或下坡，骑行时需要消耗更多的体力。具体来说，在连接路口 $i$ 和路口 $j$ 的道路上骑行，需要消耗的体力为 $|H_i - H_j|$。骑行一组道路所需的体力等于骑行其中每条道路所需体力的最大值。例如，假设有 3 条道路，骑行它们分别需要消耗 10、12 和 7 的体力，那么骑行经过所有这些道路所需的体力为 $\max(10, 12, 7) = 12$。

从路口 $i$ 出发的骑行路线定义为：从路口 $i$ 出发，经过一个或多个其他路口，且不重复使用同一条道路，最后回到路口 $i$ 的环路。

Ahmad 希望找到从每个路口出发且所需体力最小的骑行路线，这就是本题的任务。对于每个路口，你需要输出从该路口出发且所需体力最小的骑行路线的体力值。如果从某个路口出发无法完成骑行路线，则该路口的输出应为 $-1$。

例如，设 $N = 8$，$H_{1..8} = \{5, 2, 7, 0, 10, 6, 6, 6\}$，$M = 11$，道路如下图所示。节点上的标签表示路口编号，边上的数字表示骑行该道路所需的体力。注意，骑行每条道路所需的体力可以根据给定的 $H_{1..8}$ 计算得出。

从每个路口出发且所需体力最小的骑行路线如下： 路口 1：$1 \to 2 \to 7 \to 6 \to 1$，所需体力为 4。 路口 2：$2 \to 1 \to 6 \to 7 \to 2$，所需体力为 4。 路口 3：$3 \to 2 \to 1 \to 3$，所需体力为 5。 从路口 4 出发不存在可能的骑行路线。 路口 5：$5 \to 3 \to 1 \to 2 \to 5$，所需体力为 8。 路口 6：$6 \to 7 \to 8 \to 6$，所需体力为 0。 路口 7：$7 \to 8 \to 6 \to 7$，所需体力为 0。 路口 8：$8 \to 6 \to 7 \to 8$，所需体力为 0。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$ ($2 \le N \le 100\,000$; $N - 1 \le M \le 200\,000$)，分别表示路口的数量和双向道路的数量。第二行包含 $N$ 个整数 $H_i$ ($0 \le H_i \le 10^9$)，表示第 $i$ 个路口的高度。接下来的 $M$ 行，每行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i < v_i \le N$)，表示连接路口 $u_i$ 和 $v_i$ 的一条双向道路。保证从任何一个路口出发都能通过一条或多条道路到达其他任何路口。同时保证对于任意一对路口 $(u, v)$，最多只有一条双向道路连接它们。

输出格式

输出包含一行 $N$ 个整数，以空格分隔。第 $i$ 个整数表示从路口 $i$ 出发且所需体力最小的骑行路线的体力值。如果从路口 $i$ 出发不存在可能的骑行路线，则第 $i$ 个整数为 $-1$。

样例

样例输入 1

8 11
5 2 7 0 10 6 6 6
1 2
1 3
2 3
2 4
2 5
2 7
3 5
1 6
6 7
6 8
7 8

样例输出 1

4 4 5 -1 8 0 0 0

说明 1

这是题目描述中的示例。

样例输入 2

4 5
10 20 30 40
1 2
1 3
1 4
2 3
3 4

样例输出 2

20 20 20 30

样例输入 3

5 4
72 35 22 49 108
1 2
2 3
3 4
4 5

样例输出 3

-1 -1 -1 -1 -1