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;
template <typename T>
void prt(T *a, int n, bool withid = 0) {
  if (!withid)
    for (int i = 0; i < n; i++) cout << a[i] << ((i == n - 1) ? '\n' : ' ');
  else
    for (int i = 0; i < n; i++) cout << i << ": " << a[i] << '\n';
}
template <typename T>
T ceil(T a, T b) {
  return (a + b - 1) / b;
}
template <typename T>
T gcd(T x, T y) {
  return !x ? y : gcd(y % x, x);
}
template <typename T>
void exgcd(T a, T b, T &x, T &y) {
  if (!b) {
    x = 1;
    y = 0;
    return;
  }
  exgcd(b, a % b, y, x);
  y -= a / b * x;
}
long long qp(long long a, long long p) {
  if (p < 0) return 0;
  long long ans = 1;
  while (p) {
    if (p & 1) ans = ans * a;
    a = a * a;
    p >>= 1;
  }
  return ans;
}
long long qp(long long a, long long p, long long M) {
  long long ans = 1;
  while (p) {
    if (p & 1) ans = ans * a % M;
    a = a * a % M;
    p >>= 1;
  }
  return (ans % M + M) % M;
}
int euler(int *prime, int *vis, int n) {
  int top = 0;
  for (int i = 0; i <= n; i++) vis[i] = 0;
  for (int i = 2; i <= n; i++) {
    if (!vis[i]) prime[top++] = i;
    for (int j = 0; j < top && i * prime[j] <= n; j++) {
      vis[i * prime[j]] = 1;
      if (i % prime[j] == 0) break;
    }
  }
  return top;
}
struct star {
  int to, next, w;
};
const int maxn = 1e5 + 10;
const int M = 1e5 * 20 * 4;
int n;
int head[maxn], top = 0, root[maxn];
star edge[maxn << 2];
void add(int u, int v) {
  edge[top].to = v;
  edge[top].next = head[u];
  head[u] = top++;
}
struct NODE {
  int mx;
  long long sum;
};
NODE st[M];
int ls[M], rs[M], cnt = 1;
void update(int &p, int l, int r, int k) {
  if (!p) p = cnt++;
  if (l == r && l == k) {
    st[p].mx = 1;
    st[p].sum = k;
    return;
  }
  if (k <= ((l + r) >> 1)) {
    update(ls[p], l, ((l + r) >> 1), k);
    st[p] = st[ls[p]];
  } else {
    update(rs[p], ((l + r) >> 1) + 1, r, k);
    st[p] = st[rs[p]];
  }
}
void up(int p) {
  if (st[ls[p]].mx > st[rs[p]].mx)
    st[p] = st[ls[p]];
  else if (st[ls[p]].mx < st[rs[p]].mx)
    st[p] = st[rs[p]];
  else {
    st[p].mx = st[ls[p]].mx;
    st[p].sum = st[ls[p]].sum + st[rs[p]].sum;
  }
}
int merge(int r1, int r2, int l, int r) {
  if (!r1) return r2;
  if (!r2) return r1;
  if (l == r) {
    st[r1].mx += st[r2].mx;
    return r1;
  }
  ls[r1] = merge(ls[r1], ls[r2], l, ((l + r) >> 1));
  rs[r1] = merge(rs[r1], rs[r2], ((l + r) >> 1) + 1, r);
  up(r1);
  return r1;
}
long long ans[maxn];
void dfs(int now, int par) {
  for (int i = head[now]; ~i; i = edge[i].next) {
    int to = edge[i].to;
    if (to == par) continue;
    dfs(to, now);
    root[now] = merge(root[now], root[to], 1, n);
  }
  ans[now] = st[root[now]].sum;
}
int main() {
  memset((head), -1, sizeof(head));
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int c;
    scanf("%d", &c);
    update(root[i], 1, n, c);
  }
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    add(u, v);
    add(v, u);
  }
  dfs(1, 0);
  prt(ans + 1, n);
  return 0;
}
