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.DataInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;

public class Solution {
    InputStream is;
    static PrintWriter out;

    void run() {
        is = new DataInputStream(System.in);
        out = new PrintWriter(System.out);
        int t = 1;
        while (t-- > 0) solve();
        out.flush();
    }


    private void solve() {
        int n = ni();
        int[] color = na(n);
        ArrayList[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<Integer>();
        }

        for (int i = 0; i < n - 1; i++) {
            int u = ni() - 1, v = ni() - 1;
            adj[u].add(v);
            adj[v].add(u);
        }

        boolean[] vis = new boolean[n];
        long[] ans = new long[n];
        dfs(0, adj, vis, ans, color);

        for (long res : ans) {
            out.print(res + " ");
        }
    }

    public static Result dfs(int u, ArrayList<Integer>[] adj, boolean[] vis, long[] ans, int[] color) {
        vis[u] = true;
        Result r1 = null;
        for (int v : adj[u]) {
            if (!vis[v]) {
                Result r2 = dfs(v, adj, vis, ans, color);
                r1 = Result.mergeSmallInLarge(r1, r2);
            }
        }
        if (r1 == null) {
            r1 = Result.initialize(color[u]);
        } else {
            r1 = r1.add(color[u]);
        }

        ans[u] = r1.colorCountSum.last().sum;
//        System.out.println(u);
//        System.out.println(r1);
        return r1;
    }

    public static void main(String[] args) throws Exception {
        new Solution().run();
    }

    //Fast I/O code is copied from uwi code.
    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0, ptrbuf = 0;

    private int readByte() {
        if (lenbuf == -1) throw new InputMismatchException();
        if (ptrbuf >= lenbuf) {
            ptrbuf = 0;
            try {
                lenbuf = is.read(inbuf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (lenbuf <= 0) return -1;
        }
        return inbuf[ptrbuf++];
    }

    private boolean isSpaceChar(int c) {
        return !(c >= 33 && c <= 126);
    }

    private int skip() {
        int b;
        while ((b = readByte()) != -1 && isSpaceChar(b)) ;
        return b;
    }

    private double nd() {
        return Double.parseDouble(ns());
    }

    private char nc() {
        return (char) skip();
    }

    private String ns() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    private char[] ns(int n) {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while (p < n && !(isSpaceChar(b))) {
            buf[p++] = (char) b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }

    private char[][] nm(int n, int m) {
        char[][] map = new char[n][];
        for (int i = 0; i < n; i++) map[i] = ns(m);
        return map;
    }

    private int[] na(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = ni();
        return a;
    }

    private int ni() {
        int num = 0, b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        while (true) {
            if (b >= '0' && b <= '9') {
                num = num * 10 + (b - '0');
            } else {
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    private long nl() {
        long num = 0;
        int b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        while (true) {
            if (b >= '0' && b <= '9') {
                num = num * 10 + (b - '0');
            } else {
                return minus ? -num : num;
            }
            b = readByte();
        }
    }

    static class Result {
        public Map<Integer, Integer> colorCount;
        public TreeSet<Pair> colorCountSum;

        public static Result mergeSmallInLarge(Result r1, Result r2) {
            if (r1 == null) return r2;
            if (r2 == null) return r1;

            TreeSet<Pair> resColorCountSum = null;
            if (r1.colorCount.size() <= r2.colorCount.size()) {
                resColorCountSum = mergeSet(r2.colorCountSum, r1.colorCount, r2.colorCount);
            } else {
                resColorCountSum = mergeSet(r1.colorCountSum, r2.colorCount, r1.colorCount);
            }

            Map<Integer, Integer> resColorCount = null;
            if (r1.colorCount.size() <= r2.colorCount.size())
                resColorCount = mergeMap(r1.colorCount, r2.colorCount);
            else
                resColorCount = mergeMap(r2.colorCount, r1.colorCount);


            return new Result(resColorCount, resColorCountSum);
        }

        private static TreeSet<Pair> mergeSet(TreeSet<Pair> ccs2, Map<Integer, Integer> c1, Map<Integer, Integer> c2) {
            for (Map.Entry<Integer, Integer> entry : c1.entrySet()) {
                int color = entry.getKey();
                int valFromSmall = entry.getValue();
                int totalCount = valFromSmall;
                if (c2.containsKey(color)) {
                    totalCount += c2.get(color);
                    Pair ceiling = ccs2.ceiling(new Pair(c2.get(color), 0));
                    ceiling.sum -= (long) color;
                    if (ceiling.sum == 0) {
                        ccs2.remove(ceiling);
                    }
                }

                if (ccs2.ceiling(new Pair(totalCount, 0)) != null) {
                    Pair ceiling = ccs2.ceiling(new Pair(totalCount, 0));
                    if (ceiling.count == totalCount)
                        ceiling.sum += (long) color;
                    else
                        ccs2.add(new Pair(totalCount, color));
                } else {
                    ccs2.add(new Pair(totalCount, color));
                }
            }
            return ccs2;
        }

        private static Map<Integer, Integer> mergeMap(Map<Integer, Integer> c1, Map<Integer, Integer> c2) {
            for (Map.Entry<Integer, Integer> entry : c1.entrySet()) {
                int key = entry.getKey();
                int val = entry.getValue();
                if (c2.containsKey(key)) {
                    c2.put(key, c2.get(key) + val);
                } else {
                    c2.put(key, val);
                }
            }
            return c2;
        }

        public Result(Map<Integer, Integer> colorCount, TreeSet<Pair> colorCountSum) {
            this.colorCount = colorCount;
            this.colorCountSum = colorCountSum;
        }

        public Result() {
            colorCount = new HashMap<>();
            colorCountSum = new TreeSet<>();
        }

        public Result add(int color) {
            Result temp = initialize(color);
            return mergeSmallInLarge(temp, this);
        }

        public static Result initialize(int color) {
            Result result = new Result();
            result.colorCount.put(color, 1);
            result.colorCountSum.add(new Pair(1, color));
            return result;
        }

        @Override
        public String toString() {
            return "Result{" +
                    "colorCount=" + colorCount +
                    ", colorCountSum=" + colorCountSum +
                    '}';
        }
    }

    static class Pair implements Comparable<Pair> {
        public int count;
        public long sum;

        public Pair(int count, int sum) {
            this.count = count;
            this.sum = sum;
        }

        @Override
        public int compareTo(Pair o) {
            return this.count - o.count;
        }

        @Override
        public String toString() {
            return "Pair{" +
                    "count=" + count +
                    ", sum=" + sum +
                    '}';
        }
    }
}