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>
#pragma GCC optimize("O3")
using namespace std;
const long long INF = 2e9;
const long long MOD = 1e9 + 7;
const long long MB = 20;
vector<vector<long long>> g;
vector<long long> a, s;
void dfs(long long v, long long p = -1) {
  a.push_back(v);
  s[v] = 1;
  for (long long u : g[v]) {
    if (u != p) {
      dfs(u, v);
      s[v] += s[u];
    }
  }
}
bool cmp(pair<long long, pair<long long, long long>>& one,
         pair<long long, pair<long long, long long>>& two) {
  return one.second.second < two.second.second;
}
void solve() {
  long long n;
  cin >> n;
  vector<long long> b(n);
  for (long long i = 0; i < n; i++) {
    cin >> b[i];
    b[i]--;
  }
  g.resize(n);
  for (long long i = 0; i < n - 1; i++) {
    long long from, to;
    cin >> from >> to;
    from--;
    to--;
    g[from].push_back(to);
    g[to].push_back(from);
  }
  s.resize(n);
  dfs(0);
  long long k = 300;
  vector<vector<pair<long long, pair<long long, long long>>>> q(n / k + 1);
  for (long long i = 0; i < n; i++) {
    long long id = a[i];
    long long l = i;
    long long r = l + s[id] - 1;
    q[l / k].push_back({id, {l, r}});
  }
  for (long long i = 0; i < q.size(); i++) {
    sort(q[i].begin(), q[i].end(), cmp);
  }
  for (long long& i : a) i = b[i];
  vector<long long> ans(n);
  for (long long i = 0; i < q.size(); i++) {
    if (q[i].empty()) continue;
    long long left = q[i][0].second.first;
    long long right = q[i][0].second.second;
    long long mx = 0;
    vector<long long> now(n);
    vector<long long> bb(n + 1);
    for (long long j = left; j <= right; j++) {
      long long id = a[j];
      bb[now[id]] -= (id + 1);
      now[id]++;
      bb[now[id]] += (id + 1);
      if (now[id] > mx) {
        mx = now[id];
      }
    }
    for (auto& p : q[i]) {
      long long l = p.second.first;
      long long r = p.second.second;
      while (right < r) {
        right++;
        long long id = a[right];
        bb[now[id]] -= (id + 1);
        now[id]++;
        bb[now[id]] += (id + 1);
        if (now[id] > mx) {
          mx = now[id];
        }
      }
      while (left < l) {
        long long id = a[left];
        bb[now[id]] -= (id + 1);
        if (!bb[now[id]] && mx == now[id]) mx--;
        now[id]--;
        bb[now[id]] += (id + 1);
        left++;
      }
      while (left > l) {
        left--;
        long long id = a[left];
        bb[now[id]] -= (id + 1);
        now[id]++;
        bb[now[id]] += (id + 1);
        if (now[id] > mx) {
          mx = now[id];
        }
      }
      ans[p.first] = bb[mx];
    }
  }
  for (long long i : ans) cout << i << " ";
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cout.precision(12);
  solve();
}
