Problem A
Agar.IO

There are $n$ players in an agar-io game. The $i^{th}$ player has an initial size of $a_ i$. There are $m$ pairs of players, where the $i^{th}$ pair represents that players $u_ i$ and $v_ i$ adjacent to each other. Note that unlike the 2d game, our agar-io game is on a connected undirected graph.

Let the current size of player $i$ be denoted by $b_ i$. If players $u\neq v$ are adjacent, then player $u$ can eat player $v$ iff $b_ u \geq b_ v$. Afterwards, $b_ u$ increases by $b_ v$ and player $v$’s adjacent players are also adjacent to player $u$. A similar situation is possible if we swap $v$ and $u$.

A player can eat adjacent players one after the other, accumulating the sizes of eaten players. This process ends when all remaining players (if any) have larger size. Your task is to find for each player $i$, when starting as player $i$, the maximum possible final size of player $i$.

Input

The first line contains two integers $n$ and $m$ $(1\leq n\leq 300\, 000; n-1 \leq m\leq 500\, 000)$ — the number of players and the number of adjacent pairs of players.

The second line contains n integers $a_1,a_2,\ldots ,a_ n$ $(1\leq a_ i\leq 10^9)$, where $a_ i$ is the initial size of player $i$.

The $i^{th}$ of the following $m$ lines contains two integers $u_ i, v_ i$ $(1 \leq u_ i \neq v_ i \leq n)$, where $u_ i,v_ i$ are adjacent players. It is guaranteed that the undirected graph is connected.

Output

Print $n$ integers in one line: For each player $i$, print the maximum possible final size of player $i$.

4 3
1 2 3 2
1 2
2 3
3 4

1 8 8 2

7 7
5 1 3 4 2 1 4
1 2
1 3
1 4
2 5
2 6
3 7
1 7

20 4 3 4 4 4 20