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.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.TreeMap;
import java.util.Map;
import java.util.Map.Entry;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author sumit
 */
public class Main {
      public static void main(String[] args) {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            InputReader in = new InputReader(inputStream);
            OutputWriter out = new OutputWriter(outputStream);
            TaskE solver = new TaskE();
            solver.solve(1, in, out);
            out.close();
      }

      static class TaskE {
            int[] col;
            ArrayList<Integer>[] list;
            int[] sz;
            int[] cnt;
            long[] val;
            TreeMap<Integer, Integer>[] map;

            void update(int u, int va, int count) {
                  int temp = map[u].getOrDefault(va, 0);
                  temp += count;
                  map[u].put(va, temp);
                  if (temp == cnt[u]) {
                        val[u] += va;
                  } else if (temp > cnt[u]) {
                        val[u] = va;
                        cnt[u] = temp;
                  }
            }

            void dfs(int v, int p) {
                  int mx = -1;
                  int bCh = -1;
                  sz[v] = 1;
                  for (int temp : list[v])
                        if (temp != p) {
                              dfs(temp, v);
                              sz[v] += sz[temp];
                              if (sz[temp] > mx) {
                                    mx = sz[temp];
                                    bCh = temp;
                              }
                        }
                  if (bCh == -1) {
                        map[v] = new TreeMap<>();
                  } else {
                        cnt[v] = cnt[bCh];
                        val[v] = val[bCh];
                        map[v] = map[bCh];
                  }
                  update(v, col[v], 1);
                  for (int temp : list[v])
                        if (temp != p && temp != bCh) {
                              for (Map.Entry<Integer, Integer> eset : map[temp].entrySet()) {
                                    update(v, eset.getKey(), eset.getValue());
                              }
                        }


            }

            public void solve(int testNumber, InputReader in, OutputWriter out) {
                  int n = in.nextInt();
                  col = in.nextIntArray(n);
                  list = new ArrayList[n];
                  for (int i = 0; i < n; i++)
                        list[i] = new ArrayList<>();
                  for (int i = 0; i < n - 1; i++) {
                        int x = in.nextInt() - 1;
                        int y = in.nextInt() - 1;
                        list[x].add(y);
                        list[y].add(x);
                  }
                  sz = new int[n];
                  cnt = new int[n];
                  val = new long[n];
                  map = new TreeMap[n];
                  dfs(0, -1);
                  for (int i = 0; i < n; i++)
                        out.print(val[i] + " ");


            }

      }

      static class OutputWriter {
            private final PrintWriter writer;

            public OutputWriter(OutputStream outputStream) {
                  writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
            }

            public OutputWriter(Writer writer) {
                  this.writer = new PrintWriter(writer);
            }

            public void print(Object... objects) {
                  for (int i = 0; i < objects.length; i++) {
                        if (i != 0) {
                              writer.print(' ');
                        }
                        writer.print(objects[i]);
                  }
            }

            public void close() {
                  writer.close();
            }

      }

      static class InputReader {
            private InputStream stream;
            private byte[] buf = new byte[1024];
            private int curChar;
            private int numChars;

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

            public int read() {
                  if (numChars == -1)
                        throw new InputMismatchException();

                  if (curChar >= numChars) {
                        curChar = 0;
                        try {
                              numChars = stream.read(buf);
                        } catch (IOException e) {
                              throw new InputMismatchException();
                        }
                        if (numChars <= 0)
                              return -1;
                  }

                  return buf[curChar++];
            }

            public int nextInt() {
                  int c = read();

                  while (isSpaceChar(c))
                        c = read();

                  int sgn = 1;

                  if (c == '-') {
                        sgn = -1;
                        c = read();
                  }

                  int res = 0;

                  do {
                        if (c < '0' || c > '9')
                              throw new InputMismatchException();

                        res *= 10;
                        res += c & 15;

                        c = read();
                  } while (!isSpaceChar(c));

                  return res * sgn;
            }

            public int[] nextIntArray(int arraySize) {
                  int array[] = new int[arraySize];

                  for (int i = 0; i < arraySize; i++)
                        array[i] = nextInt();

                  return array;
            }

            public boolean isSpaceChar(int c) {
                  return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
            }

      }
}

