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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.List;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;

/**
 * Built using CHelper plug-in Actual solution is at the top
 *
 * @author MaxHeap
 */
public class Main {

  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    PrintWriter out = new PrintWriter(outputStream);
    ELomsatGelral solver = new ELomsatGelral();
    solver.solve(1, in, out);
    out.close();
  }

  static class ELomsatGelral {

    int[] color;
    List<Integer>[] g;
    int n;
    int[] size;
    long[] ans;
    long[] ansCount;
    long[] maxi;
    int[] count;
    boolean[] isBig;
    long sum;
    long mx;

    void calculateSize(int u, int p) {
      size[u] = 1;
      for (int v : g[u]) {
        if (v != p) {
          calculateSize(v, u);
          size[u] += size[v];
        }
      }
    }

    void add(int u, int p) {
      int c = color[u];
      count[c]++;
      if (count[c] > mx) {
        mx = count[c];
        sum = c;
      } else if (count[c] == mx) {
        sum += c;
      }
      for (int v : g[u]) {
        if (v != p && !isBig[v]) {
          add(v, u);
        }
      }
    }

    void erase(int u, int p) {
      --count[color[u]];
      for (int v : g[u]) {
        if (v != p) {
          erase(v, u);
        }
      }
    }

    void dfs(int u, int p, boolean keep) {
      int big = -1, max = -1;
      for (int v : g[u]) {
        if (v != p && size[v] > max) {
          max = size[big = v];
        }
      }
      for (int v : g[u]) {
        if (v != p && v != big) {
          dfs(v, u, false);
        }
      }
      if (big != -1) {
        dfs(big, u, true);
        isBig[big] = true;
      }
      add(u, p);
      ans[u] = sum;
      if (big != -1) {
        isBig[big] = false;
      }
      if (!keep) {
        erase(u, p);
        sum = -1;
        mx = -1;
      }
    }

    public void solve(int testNumber, InputReader in, PrintWriter out) {
      n = in.nextInt();
      g = GraphUtils.generateGraph(n);
      size = new int[n];
      color = in.nextIntArray(n);
      for (int i = 0; i < n - 1; i++) {
        int u = in.nextInt() - 1;
        int v = in.nextInt() - 1;
        g[u].add(v);
        g[v].add(u);
      }
      count = new int[n + 1];
      ans = new long[n];
      maxi = new long[n];
      ansCount = new long[n];
      isBig = new boolean[n];
      calculateSize(0, -1);
      dfs(0, -1, true);
      for (int i = 0; i < n; ++i) {
        if (i > 0) {
          out.print(" ");
        }
        out.print(ans[i]);
      }
    }

  }

  static class InputReader implements FastIO {

    private InputStream stream;
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static final int EOF = -1;
    private byte[] buf = new byte[DEFAULT_BUFFER_SIZE];
    private int curChar;
    private int numChars;

    public InputReader(InputStream stream) {
      this.stream = stream;
    }

    public int read() {
      if (this.numChars == EOF) {
        throw new UnknownError();
      } else {
        if (this.curChar >= this.numChars) {
          this.curChar = 0;

          try {
            this.numChars = this.stream.read(this.buf);
          } catch (IOException ex) {
            throw new InputMismatchException();
          }

          if (this.numChars <= 0) {
            return EOF;
          }
        }

        return this.buf[this.curChar++];
      }
    }

    public int nextInt() {
      int c;
      for (c = this.read(); isSpaceChar(c); c = this.read()) {
      }

      byte sgn = 1;
      if (c == 45) {
        sgn = -1;
        c = this.read();
      }

      int res = 0;

      while (c >= 48 && c <= 57) {
        res *= 10;
        res += c - 48;
        c = this.read();
        if (isSpaceChar(c)) {
          return res * sgn;
        }
      }

      throw new InputMismatchException();
    }

    public static boolean isSpaceChar(int c) {
      return c == 32 || c == 10 || c == 13 || c == 9 || c == EOF;
    }

    public int[] nextIntArray(int n) {
      int[] arr = new int[n];
      for (int i = 0; i < n; i++) {
        arr[i] = nextInt();
      }
      return arr;
    }

  }

  static interface FastIO {

  }

  static class GraphUtils {

    private GraphUtils() {
    }

    public static <T> List<T>[] generateGraph(int n) {
      List<T>[] graph = new ArrayList[n];
      for (int i = 0; i < n; i++) {
        graph[i] = new ArrayList<>();
      }
      return graph;
    }

  }
}

