Problem: Problem

A large-scale cluster † type supercomputer (commonly known as "SAKURA") cluster at Maze University consists of $ N $ computers (nodes) and $ M $ physical communication channels that can communicate with each other. .. In addition, each node is assigned an identification number from 1 to $ N $.

This time, the use of SAKURA will be approved not only by university personnel but also by companies in the prefecture. Along with that, it is necessary to inspect each node that composes SAKURA. However, since the usage schedule of SAKURA is filled up to several months ahead, the entire system cannot be stopped even during the inspection. Therefore, inspect the nodes one by one a day.

The inspection takes place over $ N $ days and inspects the node $ i $ on the $ i $ day. At this time, the node to be inspected and the communication path directly connected to that node are separated from the SAKURA cluster. As a result, the entire cluster of SAKURA is divided into one or more clusters, and one of them is operated in place of SAKURA. Naturally, the node under inspection cannot be operated.

When divided into multiple clusters, only the cluster with the highest "overall performance value" is operated. The "total performance value" of each cluster is the sum of the "single performance values" set for each node that composes it.

Since the number of nodes that make up SAKURA, the number of communication channels, and the "single performance value" set for each node are given, the "total performance value" of the cluster operated during the inspection on the $ i $ day is output. Let's do it.

†: A cluster is a system that combines one or more computers into a single unit. Here, it is a set of nodes connected by a physical communication path.

Constraints

The input satisfies the following conditions.

* $ 2 \ leq N \ leq 10 ^ 5 $
* $ N-1 \ leq M \ leq min (\ frac {N \ times (N-1)} {2}, 10 ^ 5) $
* $ 1 \ leq w_i \ leq 10 ^ 6 $
* $ 1 \ leq u_i, v_i \ leq N, u_i \ ne v_i $
* $ (u_i, v_i) \ ne (u_j, v_j), (u_i, v_i) \ ne (v_j, u_j), i \ ne j $
* All inputs are integers

Input

The input is given in the following format.

$ N $ $ M $
$ w_1 $ $ w_2 $ ... $ w_N $
$ u_1 $ $ v_1 $
$ u_2 $ $ v_2 $
...
$ u_M $ $ v_M $


The number of nodes that make up the cluster $ N $ and the number of communication channels $ M $ are given on the first line, separated by blanks.
In the second line, $ N $ integers representing the "single performance value" of each node are given, separated by blanks. The $ i $ th integer $ w_i $ represents the "single performance value" of the node $ i $.
The $ M $ lines from the third line are given the identification numbers of the two nodes that each channel connects, separated by blanks. The input on the 2 + $ i $ line indicates that the channel connects the node $ u_i $ and the node $ v_i $ to each other.

Output

The output consists of $ N $ lines.
In the $ i $ line, the "total performance value" of the cluster operated on the $ i $ day is output.

Examples

Input

9 10
1 2 3 4 5 6 7 8 9
1 2
2 3
2 4
3 4
4 5
4 6
2 7
7 8
7 9
9 1


Output

44
25
42
30
40
39
30
37
36


Input

16 19
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 2
2 3
3 4
3 5
1 6
6 7
6 8
7 8
8 9
8 10
10 11
11 12
12 10
1 13
13 14
14 15
15 13
14 16
15 16


Output

63
122
124
132
131
73
129
86
127
103
125
124
78
122
121
120


Input

2 1
1 2
1 2


Output

2
1

Solution (in CPP):

Solution:
#include<bits/stdc++.h>

using namespace std;


typedef long long int64;

int N, M, W[100000];
vector< int > g[100000];

bool v[100000];
int order[100000], low[100000], ptr;
int64 sum[100000], ans[100000];
vector< int > tree[100000];

void dfs(int idx, int par)
{
  v[idx] = true;
  order[idx] = ptr++;
  low[idx] = order[idx];
  sum[idx] = W[idx];
  for(auto &to : g[idx]) {
    if(!v[to]) {
      dfs(to, idx);
      low[idx] = min(low[idx], low[to]);
      sum[idx] += sum[to];
      tree[idx].emplace_back(to);
    } else if(to != par) {
      low[idx] = min(low[idx], order[to]);
    }
  }
}

void dfs2(int idx, int64 parcost)
{
  bool art = false;
  int64 all = parcost;
  if(idx == 0) {
    if(tree[idx].size() > 1) art = true;
    else art = false;
  } else {
    for(auto &to : tree[idx]) art |= order[idx] <= low[to];
  }
  for(auto &to : tree[idx]) all += sum[to];
  if(art) {
    int64 latte = parcost, malta = 0;
    for(auto &to : tree[idx]) {
      if(order[idx] <= low[to]) malta = max(malta, sum[to]);
      else latte += sum[to];
    }
    ans[idx] = max(latte, malta);
  } else {
    ans[idx] = sum[0] - W[idx];
  }
  for(auto &to : tree[idx]) dfs2(to, all + W[idx] - sum[to]);
}

int main()
{
  cin >> N >> M;
  for(int i = 0; i < N; i++) {
    cin >> W[i];
  }
  for(int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
  dfs(0, -1);
  dfs2(0, 0);
  for(int i = 0; i < N; i++) {
    cout << ans[i] << endl;
  }
}