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 ll = long long;
using namespace std;
const ll N = 1e5;
ll n;
ll c[N];
vector<ll> con[N];
ll ans[N];
void input() {
  cin >> n;
  for (ll i = 0; i < n; i++) {
    cin >> c[i];
  }
  ll a, b;
  for (ll i = 0; i < n - 1; i++) {
    cin >> a >> b;
    con[a - 1].push_back(b - 1);
    con[b - 1].push_back(a - 1);
  }
}
void output() {
  for (ll i = 0; i < n; i++) {
    cout << ans[i] << ' ';
  }
  cout << endl;
}
ll sub[N];
ll calcSub(ll curr, ll par) {
  for (ll to : con[curr]) {
    if (to == par) {
      continue;
    }
    sub[curr] += calcSub(to, curr);
  }
  return ++sub[curr];
}
void mergeSort(map<ll, ll> &mp1, map<ll, ll> &mp2, pair<ll, ll> &cans) {
  for (auto id : mp2) {
    auto &id2 = mp1[id.first];
    id2 += id.second;
    if (id2 > cans.second) {
      cans.first = id.first;
      cans.second = id2;
    } else if (id2 == cans.second) {
      cans.first += (ll)id.first;
    }
  }
  mp2.clear();
}
pair<ll, ll> dfs(ll curr, ll par, map<ll, ll> &mp) {
  ll wh = 0, big = 0;
  for (ll i = 0; i < con[curr].size(); i++) {
    if (par != con[curr][i] && big < sub[con[curr][i]]) {
      big = sub[con[curr][i]];
      wh = con[curr][i];
    }
  }
  map<ll, ll> mp2;
  pair<ll, ll> cans = {0ll, 0};
  for (ll to : con[curr]) {
    if (to == par || wh == to) {
      continue;
    }
    dfs(to, curr, mp2);
    mergeSort(mp, mp2, cans);
  }
  if (big) {
    swap(mp, mp2);
    cans = dfs(wh, curr, mp);
    mergeSort(mp, mp2, cans);
  }
  auto &id2 = mp[c[curr]];
  id2++;
  if (id2 > cans.second) {
    cans.first = c[curr];
    cans.second = id2;
  } else if (id2 == cans.second) {
    cans.first += (ll)c[curr];
  }
  ans[curr] = cans.first;
  return cans;
}
void solve() {
  calcSub(0, 0);
  map<ll, ll> mp;
  dfs(0, 0, mp);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  input();
  solve();
  output();
  return 0;
}
