You are given a rooted tree with root in vertex 1. Each vertex is coloured in some colour.

Let's call colour c dominating in the subtree of vertex v if there are no other colours that appear in the subtree of vertex v more times than colour c. So it's possible that two or more colours will be dominating in the subtree of some vertex.

The subtree of vertex v is the vertex v and all other vertices that contains vertex v in each path to the root.

For each vertex v find the sum of all dominating colours in the subtree of vertex v.

Input

The first line contains integer n (1 ≤ n ≤ 105) — the number of vertices in the tree.

The second line contains n integers ci (1 ≤ ci ≤ n), ci — the colour of the i-th vertex.

Each of the next n - 1 lines contains two integers xj, yj (1 ≤ xj, yj ≤ n) — the edge of the tree. The first vertex is the root of the tree.

Output

Print n integers — the sums of dominating colours for each vertex.

Examples

Input

4
1 2 3 4
1 2
2 3
2 4


Output

10 9 3 4


Input

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


Output

6 5 4 3 2 3 3 1 1 3 2 2 1 2 3
#include <bits/stdc++.h>
using namespace std;
inline void read(int &x) {
  register int c = getchar();
  x = 0;
  int neg = 0;
  for (; ((c < 48 || c > 57) && c != '-'); c = getchar())
    ;
  if (c == '-') {
    neg = 1;
    c = getchar();
  }
  for (; c > 47 && c < 58; c = getchar()) {
    x = (x << 1) + (x << 3) + c - 48;
  }
  if (neg) x = -x;
}
inline void writeln(int x) {
  char buffor[21];
  register int i = 0;
  int neg = 0;
  if (x < 0) {
    neg = 1;
    x = -x;
  }
  do {
    buffor[i++] = (x % 10) + '0';
    x /= 10;
  } while (x);
  i--;
  if (neg) putchar('-');
  while (i >= 0) putchar(buffor[i--]);
  putchar('\n');
}
const int N = (int)1e5 + 10;
int n, col[N];
vector<int> a[N];
int cnt[N], sz[N], st[N], fi[N], ver[N], cc;
int maxx;
long long sum;
long long res[N];
void input() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> col[i];
  for (int i = 1; i <= n - 1; i++) {
    int u, v;
    cin >> u >> v;
    a[u].push_back(v);
    a[v].push_back(u);
  }
}
void getsz(int u, int par) {
  sz[u] = 1;
  cc++;
  st[u] = cc;
  ver[cc] = u;
  for (int i = 0; i <= (int)a[u].size() - 1; i++) {
    int v = a[u][i];
    if (v != par) {
      getsz(v, u);
      sz[u] += sz[v];
    }
  }
  fi[u] = cc;
}
void update(int cl, int v) {
  cnt[cl] += v;
  if (v == 1) {
    if (maxx < cnt[cl]) {
      maxx = cnt[cl];
      sum = cl;
    } else if (maxx == cnt[cl])
      sum += cl;
  }
}
void dfs(int u, int par, int big) {
  int maxsz = 0, bigc = -1;
  for (int i = 0; i <= (int)a[u].size() - 1; i++) {
    int v = a[u][i];
    if (v != par and sz[v] > maxsz) {
      maxsz = sz[v];
      bigc = v;
    }
  }
  for (int i = 0; i <= (int)a[u].size() - 1; i++) {
    int v = a[u][i];
    if (v != par and v != bigc) dfs(v, u, 0);
  }
  if (bigc != -1) dfs(bigc, u, 1);
  update(col[u], 1);
  for (int i = 0; i <= (int)a[u].size() - 1; i++) {
    int v = a[u][i];
    if (v != par and v != bigc) {
      for (int j = st[v]; j <= fi[v]; j++) update(col[ver[j]], 1);
    }
  }
  res[u] = sum;
  if (big == 0) {
    for (int i = st[u]; i <= fi[u]; i++) update(col[ver[i]], -1);
    maxx = sum = 0;
  }
}
void solve() {
  cc = 0;
  getsz(1, 0);
  sum = 0;
  maxx = 0;
  dfs(1, 0, 1);
  for (int i = 1; i <= n; i++) cout << res[i] << " ";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  input();
  solve();
  return 0;
}
