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;
int n, c, head[100100], b[100100], t[100100], maxn;
long long bans[100100], ansn;
struct Edge {
  int nxt, to;
} eg[200200];
struct node {
  int sz, deep, top, fa, w, id, son;
} e[100100];
void read() {
  int m1, m2;
  cin >> n;
  for (int i = 1; i <= n; i++) scanf("%d", &e[i].w);
  for (int i = 1; i < n; i++) {
    scanf("%d%d", &m1, &m2);
    eg[++c].to = m2;
    eg[c].nxt = head[m1];
    head[m1] = c;
    eg[++c].to = m1;
    eg[c].nxt = head[m2];
    head[m2] = c;
  }
}
void dfs1(int k, int dp) {
  e[k].deep = dp;
  e[k].sz = 1;
  int maxn = -0x7fffffff;
  for (int i = head[k]; i; i = eg[i].nxt) {
    if (eg[i].to == e[k].fa) continue;
    e[eg[i].to].fa = k;
    dfs1(eg[i].to, dp + 1);
    e[k].sz += e[eg[i].to].sz;
    if (e[eg[i].to].sz > maxn) {
      e[k].son = eg[i].to;
      maxn = e[eg[i].to].sz;
    }
  }
}
void dfs2(int k, int tp) {
  e[k].id = ++c;
  b[c] = e[k].w;
  e[k].top = tp;
  if (e[k].son) {
    dfs2(e[k].son, tp);
    for (int i = head[k]; i; i = eg[i].nxt) {
      if (eg[i].to == e[k].fa || eg[i].to == e[k].son) continue;
      dfs2(eg[i].to, eg[i].to);
    }
  }
}
inline long long sum(int l, int r) {
  for (int i = l; i <= r; i++) {
    t[b[i]]++;
    if (t[b[i]] == maxn)
      ansn += b[i];
    else if (t[b[i]] > maxn) {
      maxn = t[b[i]];
      ansn = b[i];
    }
  }
  return ansn;
}
void dfs3(int k) {
  if (e[k].son) {
    for (int i = head[k]; i; i = eg[i].nxt) {
      if (eg[i].to == e[k].fa || eg[i].to == e[k].son) continue;
      dfs3(eg[i].to);
      memset(t, 0, sizeof(t));
      ansn = maxn = 0;
    }
    dfs3(e[k].son);
    t[e[k].w]++;
    if (t[e[k].w] == maxn)
      ansn += e[k].w;
    else if (t[e[k].w] > maxn) {
      maxn = t[e[k].w];
      ansn = e[k].w;
    }
    bans[k] = sum(e[k].id + e[e[k].son].sz + 1, e[k].id + e[k].sz - 1);
  } else
    ansn = bans[k] = e[k].w, maxn = 1, t[e[k].w]++;
}
int main() {
  read();
  c = 0;
  dfs1(1, 1);
  dfs2(1, 1);
  dfs3(1);
  for (int i = 1; i <= n; i++) printf("%lld ", bans[i]);
}
