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.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.File;
import java.util.ArrayList;
import java.io.InputStream;

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

    static class ELomsatGelral {
        int n;
        int idx = 0;
        int[] size;
        int[] first;
        int[] last;
        int[] map;
        int[] color;
        int[] cnt;
        long[] qans;
        long[] cntsum;
        int maxOcc = 0;
        ArrayList<Integer>[] vs;

        int dfs1(int node, int par) {
            map[idx] = node;
            first[node] = idx++;
            int cur = 1;
            for (int i : vs[node])
                if (i != par) {
                    cur += dfs1(i, node);
                }
            last[node] = idx;
            return size[node] = cur;
        }

        void add(int v) {
            int curcnt = cnt[color[v]];
            cntsum[curcnt] -= color[v];
            cnt[color[v]] = ++curcnt;
            cntsum[curcnt] += color[v];
            if (maxOcc < curcnt) ++maxOcc;
        }

        void remove(int v) {
            int curcnt = cnt[color[v]];
            cntsum[curcnt] -= color[v];
            cnt[color[v]] = --curcnt;
            cntsum[curcnt] += color[v];
            if (cntsum[maxOcc] == 0) --maxOcc;
        }

        void dfs(int node, int par, boolean keep) {
            int maxChild = -1, maxSize = -1;
            for (int i : vs[node])
                if (i != par) {
                    if (size[i] > maxSize) {
                        maxSize = size[i];
                        maxChild = i;
                    }
                }
            for (int i : vs[node])
                if (i != par && i != maxChild) {
                    dfs(i, node, false);
                }
            if (maxChild != -1) dfs(maxChild, node, true);
            for (int i : vs[node])
                if (i != par && i != maxChild) {
                    for (int t = first[i]; t < last[i]; ++t) {
                        add(map[t]);
                    }
                }
            add(node);
            qans[node] = cntsum[maxOcc];
            if (!keep) {
                for (int t = first[node]; t < last[node]; ++t) {
                    remove(map[t]);
                }
            }
        }

        public void solve(int testNumber, JoltyScanner in, PrintWriter out) {
            n = in.nextInt();
            qans = new long[n];
            size = new int[n];
            first = new int[n];
            last = new int[n];
            map = new int[n];
            color = new int[n];
            cnt = new int[n + 1];
            cntsum = new long[n + 1];
            vs = new ArrayList[n];
            long totsum = 0;
            for (int i = 0; i < n; ++i) totsum += (color[i] = in.nextInt());
            for (int i = 0; i < n; ++i) vs[i] = new ArrayList<>();
            for (int i = 0; i < n - 1; ++i) {
                int u = in.nextInt() - 1;
                int v = in.nextInt() - 1;
                vs[u].add(v);
                vs[v].add(u);
            }
            cntsum[0] = totsum;
            dfs1(0, -1);
            dfs(0, -1, true);
            for (long ans : qans) out.print(ans + " ");
            out.println();
        }

    }

    static class JoltyScanner {
        public int BS = 1 << 16;
        public char NC = (char) 0;
        public byte[] buf = new byte[BS];
        public int bId = 0;
        public int size = 0;
        public char c = NC;
        public double num = 1;
        public BufferedInputStream in;

        public JoltyScanner(InputStream is) {
            in = new BufferedInputStream(is, BS);
        }

        public JoltyScanner(String s) throws FileNotFoundException {
            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
        }

        public char nextChar() {
            while (bId == size) {
                try {
                    size = in.read(buf);
                } catch (Exception e) {
                    return NC;
                }
                if (size == -1) return NC;
                bId = 0;
            }
            return (char) buf[bId++];
        }

        public int nextInt() {
            return (int) nextLong();
        }

        public long nextLong() {
            num = 1;
            boolean neg = false;
            if (c == NC) c = nextChar();
            for (; (c < '0' || c > '9'); c = nextChar()) {
                if (c == '-') neg = true;
            }
            long res = 0;
            for (; c >= '0' && c <= '9'; c = nextChar()) {
                res = (res << 3) + (res << 1) + c - '0';
                num *= 10;
            }
            return neg ? -res : res;
        }

    }
}

