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
import java.io.*;
import java.util.*;
import java.util.stream.Collectors;


public class Main {

  public static void main(String[] args) {
    solve();
  }

  final static int MAXN = 30005;
  final static int MAXK = 505;
  static int N = 0;;
  static int M = 0;
  static int K = 0;
  static int W = 0;
  static int H = 0;
  static int[] A;
  static long[][] dp;
  static int[][] pre;
  static int[][] g;
  static int curAns = Integer.MAX_VALUE;
  static long[] HASH = new long[MAXN];
  static long MOD = (1L << 50) + 7;
  static int[][] memo;
  static boolean[][] seen;

  static int[] colors;
  static List<Integer>[] edges;
  static CPair[] ans;
  static long[] cal;


  static void solve() {
    FastReader scanner = new FastReader();
    PrintWriter out = new PrintWriter(System.out);

    N = scanner.nextInt();
    colors = new int[N];
    edges = new ArrayList[N];
    ans = new CPair[N];
    cal = new long[N];
    for (int i = 0; i < N; i++) {
      edges[i] = new ArrayList<>();
    }

    for (int i = 0; i < N; i++) {
      colors[i] = scanner.nextInt();
    }

    for (int i = 0; i < N-1; i++) {
      int u = scanner.nextInt();
      int v = scanner.nextInt();
      u--;
      v--;
      edges[u].add(v);
      edges[v].add(u);
    }


    dfs(0, -1);

    StringBuilder s = new StringBuilder();
    for (int i = 0; i < N; i++) {
      s.append(cal[i]);
      if (i < N-1) s.append(" ");
    }
    out.println(s.toString());
    out.close();
  }

  public static void merge(CPair a, CPair b) {
    for (Map.Entry<Integer, Integer> entry: b.a.entrySet()) {
      int k = entry.getKey();
      int v = entry.getValue();
      a.a.put(k, a.a.getOrDefault(k, 0) + v);

      v = a.a.get(k);
      if (v > a.max_count) {
        a.max_count = v;
        a.sum = k;
      } else if (v == a.max_count) {
        a.sum += k;
      }
    }
  }


  public static void dfs(int curr, int parent) {
    for (int v: edges[curr]) {
      if (v != parent) {
        dfs(v, curr);
      }
    }

    int id = -1;
    int maxsize = -1;
    for (int to: edges[curr]) {
      if (to == parent) continue;
      if (maxsize < ans[to].a.size()) {
        maxsize = ans[to].a.size();
        id = to;
      }
    }

    CPair ansv = new CPair();
    if (id != -1) {
      ansv = ans[id];
//      merge(ansv, ans[id]);
    }

    for (int to: edges[curr]) {
      if (to == parent || to == id) continue;
      merge(ansv, ans[to]);
    }

    CPair t = new CPair();
    t.max_count = 1;
    t.sum = colors[curr];
    t.a.put(colors[curr], 1);
    merge(ansv, t);

    ans[curr] = ansv;
    cal[curr] = ansv.sum;
  }


  public static class FastReader {
    BufferedReader br;
    StringTokenizer st;


    public FastReader() {
      br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
      while (st == null || !st.hasMoreTokens()) {
        try {
          st = new StringTokenizer(br.readLine());
        } catch (Exception r) {
          r.printStackTrace();
        }
      }
      return st.nextToken();
    }

    int nextInt() {
      return Integer.parseInt(next());//converts string to integer
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    long nextLong() {
      return Long.parseLong(next());
    }

    String nextLine() {
      String str = "";
      try {
        str = br.readLine();
      } catch (Exception r) {
        r.printStackTrace();
      }
      return str;
    }
  }
}

class CPair {
  public int max_count = 0;
  public long sum = 0;
  public TreeMap<Integer, Integer> a = new TreeMap<>();
}

class UnioinSet {
  private Map<Long, Long> parents = new HashMap<>();

  public Long find(Long u) {
    if (parents.getOrDefault(u, u).equals(u)) {
      return u;
    }

    return find(parents.get(u));
  }

  public void union(Long u, Long v) {
    Long pu = find(u);
    Long pv = find(v);

    parents.put(pu, pv);
  }
}


class Pair<A, B> implements Comparable<Pair<A, B>>{
  private A first;
  private B second;

  public Pair(A first, B second) {
    super();
    this.first = first;
    this.second = second;
  }

  public String toString()
  {
    return "(" + first + ", " + second + ")";
  }

  public A getFirst() {
    return first;
  }

  public void setFirst(A first) {
    this.first = first;
  }

  public B getSecond() {
    return second;
  }

  public void setSecond(B second) {
    this.second = second;
  }

  @Override
  public int compareTo(Pair<A, B> o) {
    int cmp = compare(first, o.first);
    return cmp == 0 ? compare(second, o.second) : cmp;
  }

  private static int compare(Object o1, Object o2) {
    return o1 == null ? o2 == null ? 0 : -1 : o2 == null ? +1
      : ((Comparable) o1).compareTo(o2);
  }

  @Override
  public int hashCode() {
    return 31 * hashcode(first) + hashcode(second);
  }

  private static int hashcode(Object o) {
    return o == null ? 0 : o.hashCode();
  }

  public boolean equals(Object other) {
    if (other instanceof Pair) {
      Pair<A, B> otherPair = (Pair<A, B>) other;
      return
        ((  this.first == otherPair.first ||
          ( this.first != null && otherPair.first != null &&
            this.first.equals(otherPair.first))) &&
          (  this.second == otherPair.second ||
            ( this.second != null && otherPair.second != null &&
              this.second.equals(otherPair.second))) );
    }

    return false;
  }
}
