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 MaxN = 100005;
const int MaxE = 200005;
int n;
struct edge_t {
  int to;
  edge_t *next;
} edges[MaxE], *cure;
inline void add_edge(edge_t **head, int u, int v) {
  cure->to = v;
  cure->next = head[u];
  head[u] = cure++;
}
struct node_t {
  node_t *c[2], *p;
  long long sum, dsum;
  int count, dcount;
} memo[MaxN], *nil, *pt[MaxN], *st[MaxN];
struct lct_t {
  void init(node_t *x) {
    x->c[0] = x->c[1] = x->p = nil;
    x->count = 0;
    x->sum = x->dsum = 0;
    x->dcount = -1;
  }
  void init() {
    pt[0] = nil = &memo[0];
    for (int i = 1; i <= n; i++) pt[i] = &memo[i], init(pt[i]);
  }
  void rotate(node_t *x, int f) {
    node_t *y = x->p, *z = y->p;
    x->p = z, y->p = x;
    if (z != nil) {
      if (y == z->c[0])
        z->c[0] = x;
      else if (y == z->c[1])
        z->c[1] = x;
    }
    y->c[f ^ 1] = x->c[f];
    if (y->c[f ^ 1] != nil) y->c[f ^ 1]->p = y;
    x->c[f] = y;
  }
  void splay(node_t *x) {
    int top = 1;
    st[0] = x;
    for (node_t *q = x; !isroot(q);) st[top++] = (q = q->p);
    while (top) pushdown(st[--top]);
    while (!isroot(x)) {
      node_t *y = x->p;
      if (isroot(y))
        rotate(x, y->c[0] == x);
      else {
        int t = (y == y->p->c[0]);
        if (x == y->c[t])
          rotate(x, t ^ 1), rotate(x, t);
        else
          rotate(y, t), rotate(x, t);
      }
    }
  }
  void set_count(node_t *x, int count, long long sum, bool forSubTree = true) {
    if (x == nil) return;
    if (x->count < count) {
      x->count = count;
      x->sum = 0;
    }
    if (x->count == count) x->sum += sum;
    if (forSubTree) {
      if (x->dcount < count) {
        x->dcount = count;
        x->dsum = 0;
      }
      if (x->dcount == count) x->dsum += sum;
    }
  }
  void pushdown(node_t *x) {
    if (x == nil) return;
    if (x->dcount != -1) {
      set_count(x->c[0], x->dcount, x->dsum);
      set_count(x->c[1], x->dcount, x->dsum);
      x->dcount = -1;
      x->dsum = 0;
    }
  }
  bool isroot(node_t *x) {
    return x->p == nil || (x->p->c[0] != x && x->p->c[1] != x);
  }
  node_t *expose(node_t *x) {
    node_t *y;
    for (y = nil; x != nil; x = x->p) splay(x), x->c[1] = y, y = x;
    return y;
  }
  node_t *head(node_t *x) {
    if (x == nil) return nil;
    while (x->c[0] != nil) pushdown(x), x = x->c[0];
    splay(x);
    return x;
  }
  void update(node_t *x, node_t *y, int count, long long sum) {
    expose(y);
    expose(x);
    for (node_t *u = y, *v = nil; u != nil; u = u->p) {
      splay(u);
      if (u->p == nil) {
        set_count(u, count, sum, false);
        set_count(u->c[1], count, sum);
        set_count(v, count, sum);
        return;
      }
      u->c[1] = v;
      v = u;
    }
  }
  bool merge(node_t *x, node_t *y) {
    node_t *ry = head(expose(y)), *rx = head(expose(x));
    if (rx == ry)
      return false;
    else {
      splay(x), x->p = y;
      return true;
    }
  }
  node_t *lca(node_t *x, node_t *y) {
    node_t *rx = head(expose(x));
    node_t *ey = expose(y), *ry = head(ey);
    if (rx == ry)
      return ey;
    else
      return nil;
  }
  long long query(node_t *x) {
    splay(x);
    return x->sum;
  }
} tr;
edge_t *head[MaxN];
int c[MaxN], res[MaxN], dep[MaxN], id[MaxN], id2[MaxN], K, K2, size[MaxN];
struct comp_t {
  bool operator()(const int &a, const int &b) { return id[a] < id[b]; }
};
std::set<int, comp_t> nodes[MaxN];
int cur[MaxN], cur_n;
int virtual_nodes[MaxN], father[MaxN], m;
void init() {
  cure = edges;
  K = K2 = 0;
  for (int i = 1; i <= n; i++) {
    nodes[i].clear();
    head[i] = NULL;
    id[i] = 0;
  }
}
void dfs(int u) {
  int v;
  id[u] = ++K;
  for (edge_t *iter = head[u]; iter; iter = iter->next) {
    v = iter->to;
    if (id[v] == 0) {
      tr.merge(pt[v], pt[u]);
      dep[v] = dep[u] + 1;
      dfs(v);
    }
  }
  id2[u] = ++K2;
}
class TaskE {
 public:
  void solve(std::istream &in, std::ostream &out) {
    int u, v;
    in >> n;
    init();
    tr.init();
    for (int i = 1; i <= n; i++) {
      in >> c[i];
      size[i] = 1;
    }
    for (int i = 1; i < n; i++) {
      in >> u >> v;
      add_edge(head, u, v);
      add_edge(head, v, u);
    }
    dfs(1);
    for (int i = 1; i <= n; i++) nodes[c[i]].insert(i);
    for (int i = 1; i <= n; i++) {
      auto &node = nodes[i];
      m = cur_n = 0;
      for (auto x : node) {
        cur[cur_n++] = x;
        size[x] = 1;
        if (m == 0) {
          virtual_nodes[++m] = x;
          father[x] = 0;
        } else {
          int lca = (int)(tr.lca(pt[x], pt[virtual_nodes[m]]) - memo);
          while (dep[virtual_nodes[m]] > dep[lca]) {
            if (dep[virtual_nodes[m - 1]] <= dep[lca]) {
              father[virtual_nodes[m]] = lca;
            }
            m--;
          }
          if (virtual_nodes[m] != lca) {
            cur[cur_n++] = lca;
            size[lca] = 0;
            father[lca] = virtual_nodes[m];
            virtual_nodes[++m] = lca;
          }
          father[x] = lca;
          virtual_nodes[++m] = x;
        }
      }
      std::sort(cur, cur + cur_n,
                [&](const int &a, const int &b) { return id2[a] < id2[b]; });
      for (int j = 0; j < cur_n; j++) {
        tr.update(pt[cur[j]], pt[1], size[cur[j]], i);
        size[father[cur[j]]] += size[cur[j]];
      }
    }
    for (int i = 1; i <= n; i++) out << tr.query(pt[i]) << " ";
    out << std::endl;
  }
};
int main() {
  std::ios_base::sync_with_stdio(false);
  TaskE solver;
  std::istream &in(std::cin);
  std::ostream &out(std::cout);
  solver.solve(in, out);
  return 0;
}
