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>
const int N = 100010;
const long long INF = 1ll << 60;
const int inf = 0x3f3f3f3f;
class SegmentTreeCombination {
 public:
  void Init(int n, int val_max) {
    n_ = n;
    val_max_ = val_max;
    cnt = 0;
    for (int i = 1; i <= n; ++i) {
      root[i] = ++cnt;
    }
  }
  void Merge(int a, int b) { MergeImp(root[a], root[b], 1, val_max_); }
  void Update(int a, int pos, int v) {
    UpdateImp(root[a], 1, val_max_, pos, v);
  }
  long long Query(int a) { return tr[root[a]].sum_id_mx; }

 private:
  void MergeImp(int& rt_a, int& rt_b, int l, int r) {
    if (!rt_a || !rt_b) {
      rt_a |= rt_b;
      rt_b = 0;
      return;
    }
    if (l == r) {
      tr[rt_a].id = l;
      tr[rt_a].mx += tr[rt_b].mx;
      tr[rt_a].sum_id_mx = l;
      return;
    }
    int m = (l + r) >> 1;
    MergeImp(tr[rt_a].l, tr[rt_b].l, l, m);
    MergeImp(tr[rt_a].r, tr[rt_b].r, m + 1, r);
    Up(rt_a);
    rt_b = 0;
  }
  void UpdateImp(int& rt, int l, int r, int pos, int v) {
    if (!rt) rt = ++cnt;
    if (l == r) {
      tr[rt].id = l;
      tr[rt].mx += v;
      tr[rt].sum_id_mx = l;
      return;
    }
    int m = (l + r) >> 1;
    if (pos <= m)
      UpdateImp(tr[rt].l, l, m, pos, v);
    else
      UpdateImp(tr[rt].r, m + 1, r, pos, v);
    Up(rt);
  }
  void Up(int rt) {
    if (tr[tr[rt].l].mx > tr[tr[rt].r].mx) {
      tr[rt].mx = tr[tr[rt].l].mx;
      tr[rt].id = tr[tr[rt].l].id;
      tr[rt].sum_id_mx = tr[tr[rt].l].sum_id_mx;
    }
    if (tr[tr[rt].r].mx > tr[tr[rt].l].mx) {
      tr[rt].mx = tr[tr[rt].r].mx;
      tr[rt].id = tr[tr[rt].r].id;
      tr[rt].sum_id_mx = tr[tr[rt].r].sum_id_mx;
    }
    if (tr[tr[rt].l].mx == tr[tr[rt].r].mx) {
      tr[rt].mx = tr[tr[rt].l].mx;
      tr[rt].id = tr[tr[rt].l].id;
      tr[rt].sum_id_mx = tr[tr[rt].l].sum_id_mx + tr[tr[rt].r].sum_id_mx;
    }
  }
  struct Tree {
    int l, r;
    long long mx;
    int id;
    long long sum_id_mx;
  } tr[N * 50];
  int n_;
  int val_max_;
  int root[N];
  int cnt;
} seg_comb;
class Graph {
 public:
  Graph() {
    e_.clear();
    e_.push_back(Edge(0, 0, 1));
    m_ = 0;
  }
  void Init(int n) {
    e_.clear();
    e_.push_back(Edge(0, 0, 1));
    m_ = 0;
    n_ = n;
    hd_.assign(n + 1, 0);
    vis_.assign(n + 1, false);
    connected_num_ = 0;
    for (int i = 1; i <= n; ++i) {
      deg_in_[i] = 0;
    }
  }
  void Init(int n, int w[]) {
    e_.clear();
    e_.push_back(Edge(0, 0, 1));
    m_ = 0;
    n_ = n;
    hd_.assign(n + 1, 0);
    vis_.assign(n + 1, false);
    connected_num_ = 0;
    for (int i = 1; i <= n; ++i) {
      deg_in_[i] = 0;
      weight[i] = w[i];
    }
  }
  void Add(int u, int v, long long w = 1ll) {
    Edge edge(v, hd_[u], w);
    e_.push_back(edge);
    hd_[u] = ++m_;
    ++deg_in_[v];
  }
  int Head(int id_v) { return hd_[id_v]; }
  int Next(int id_e) { return e_[id_e].nxt; }
  int To(int id_e) { return e_[id_e].v; }
  long long& W(int id_e) { return e_[id_e].w; }
  int NumNode() { return n_; }
  long long WNode(int u) { return weight[u]; }

 private:
  struct Edge {
    int v, nxt;
    long long w;
    Edge(int _v, int _nxt, long long _w) : v(_v), nxt(_nxt), w(_w) {}
  };
  int n_;
  std::vector<int> hd_;
  long long weight[N];
  int m_;
  std::vector<Edge> e_;
  std::vector<bool> vis_;
  int deg_in_[N];
  int connected_num_;
};
class RootedTree {
 public:
  RootedTree() {}
  void Init(int n) {
    n_ = n;
    m_ = std::min(21, (int)ceil(log(n_) / log(2)) + 2);
    graph.Init(n);
  }
  void Init(int n, int _w[]) {
    n_ = n;
    m_ = std::min(21, (int)ceil(log(n_) / log(2)) + 2);
    graph.Init(n, _w);
  }
  void Add(int u, int v, int w = 1) {
    graph.Add(u, v, w);
    graph.Add(v, u, w);
  }
  void SetRoot(int u) { root = u; }
  void SegComb(long long sum_id_mx[]) {
    seg_comb.Init(n_, n_);
    DfsSegComb(root, root, sum_id_mx);
  }

 private:
  void DfsSegComb(int u, int fa, long long sum_id_mx[]) {
    for (int i = graph.Head(u); i; i = graph.Next(i)) {
      int v = graph.To(i);
      if (v == fa) {
        continue;
      }
      DfsSegComb(v, u, sum_id_mx);
      seg_comb.Merge(u, v);
    }
    seg_comb.Update(u, (int)graph.WNode(u), 1);
    sum_id_mx[u] = seg_comb.Query(u);
  }
  int n_;
  int m_;
  Graph graph;
  int root;
} tree;
int n, w[N];
long long sum_id_mx[N];
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &w[i]);
  }
  tree.Init(n, w);
  for (int i = 1; i < n; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    tree.Add(x, y);
  }
  tree.SetRoot(1);
  tree.SegComb(sum_id_mx);
  for (int i = 1; i <= n; ++i) {
    printf("%lld%s", sum_id_mx[i], i == n ? "\n" : " ");
  }
  return 0;
}
