题目描述

Alice is moving to the city of Nogonia, and to decide where to live, she is evaluating the safety of the city.

Nogonia is a planned city with $N$ intersections, numbered from $1$ to $N$, and $M$ streets. Each street connects two intersections bidirectionally. It is guaranteed that any intersection can reach all other intersections using the streets, and no two streets connect the same pair of intersections.

The government of Nogonia publishes a danger rating $D_i$ for each intersection $i$. However, Alice thinks these ratings are insufficient because she wants to assess the safety of moving through the city, not just where she lives. So, she developed her own way to measure how dangerous the city is.

For any given path in the city, Alice defines its path risk as the maximum danger rating among all intersections on that path, including its endpoints. The risk factor between two intersections $U$ and $V$, denoted as $f(U,V)$, is the minimum possible path risk among all paths connecting $U$ and $V$. By definition, the only path from an intersection $U$ to itself is the trivial path containing only $U$, so we have $f(U,U) = D_U$. Finally, she assigns a danger score to each intersection $U$, denoted as:

In other words, the danger score of an intersection $U$ is the sum of its risk factors to every intersection in the city.

Computing these danger scores for all intersections is not easy, so Alice asks for your help!

输入格式

The first line contains two integers $N$ ($2 \le N \le 3 \cdot 10^5$) and $M$ ($1 \le M \le 3 \cdot 10^5$), indicating respectively the number of intersections and streets in Nogonia. Each intersection is identified by a distinct integer from $1$ to $N$.

The second line contains $N$ integers $D_1, D_2, \dots, D_N$ ($1 \le D_i \le 10^9$ for $i = 1, 2, \dots, N$), where $D_i$ is the danger rating of intersection $i$.

Each of the next $M$ lines contains two integers $U$ and $V$ ($1 \le U, V \le N$ and $U \ne V$), indicating that there is a two-way street between intersections $U$ and $V$.

It is guaranteed that there is at most one street between each pair of intersections and that any intersection can be reached from any other using one or more streets.

输出格式

Output a single line with $N$ integers $S_1, S_2, \dots, S_N$, that is, the danger scores of all the intersections.

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