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

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author George Marcus
 */
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);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        ArrayList<Integer>[] A;
        long[] ans;
        int[] C;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int N = in.readInt();
            C = new int[N];
            for (int i = 0; i < N; i++) {
                C[i] = in.readInt();
            }
            A = new ArrayList[N];
            for (int i = 0; i < N; i++) {
                A[i] = new ArrayList<>();
            }
            for (int i = 0; i < N - 1; i++) {
                int a = in.readInt();
                int b = in.readInt();
                a--;
                b--;
                A[a].add(b);
                A[b].add(a);
            }

            ans = new long[N];
            go(0, -1);

            for (int i = 0; i < N; i++) {
                if (i > 0) {
                    out.print(' ');
                }
                out.print(ans[i]);
            }
            out.println();
        }

        private SpecialMap go(int node, int prev) {
            SpecialMap currentMap = new SpecialMap(C[node]);
            for (int x : A[node]) {
                if (x != prev) {
                    SpecialMap childMap = go(x, node);
                    if (currentMap.getSize() < childMap.getSize()) {
                        SpecialMap aux = currentMap;
                        currentMap = childMap;
                        childMap = aux;
                    }
                    currentMap.insert(childMap);
                }
            }
            ans[node] = currentMap.getSum();
            return currentMap;
        }

        private class SpecialMap {
            private HashMap<Integer, Integer> map;
            private int max;
            private long maxSum;

            public SpecialMap(int c) {
                map = new HashMap<>();
                max = 1;
                maxSum = c;
                map.put(c, 1);
            }

            public HashMap<Integer, Integer> getMap() {
                return map;
            }

            public int getSize() {
                return map.size();
            }

            public void insert(SpecialMap other) {
                HashMap<Integer, Integer> otherMap = other.getMap();
                for (int x : otherMap.keySet()) {
                    int newFreq = add(x, otherMap.get(x));
                    if (newFreq == max) {
                        maxSum += x;
                    } else if (newFreq > max) {
                        max = newFreq;
                        maxSum = x;
                    }
                }
            }

            private int add(int x, int val) {
                int currentFreq = 0;
                if (map.containsKey(x)) {
                    currentFreq = map.get(x);
                }
                int nextFreq = currentFreq + val;
                map.put(x, nextFreq);
                return nextFreq;
            }

            public long getSum() {
                return maxSum;
            }

        }

    }

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

        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 readInt() {
            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 - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return isWhitespace(c);
        }

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

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}

