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.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Solve6 {

    public static void main(String[] args) throws IOException {
        PrintWriter pw = new PrintWriter(System.out);
        new Solve6().solve(pw);
        pw.flush();
        pw.close();
    }

    public void solve(PrintWriter pw) throws IOException {
        FastReader sc = new FastReader();
        n = sc.nextInt();
        adj = new ArrayList[n + 1];
        children = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            adj[i] = new ArrayList();
            children[i] = new ArrayList();
        }
        size = new int[n + 1];
        color = new int[n + 1];
        coloring = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            color[i] = sc.nextInt();
        }
        for (int i = 1; i <= n - 1; i++) {
            int x = sc.nextInt(), y = sc.nextInt();
            adj[x].add(y);
            adj[y].add(x);
        }
        dfsSize(1, -1);
        ans = new long[n + 1];
        freq = new TreeMap();
        dsuOnTree(1, -1, true);
        for (int i = 1; i <= n; i++) {
            pw.print((i != 1 ? " " : "") + ans[i]);
        }
        pw.println();
    }
    int n;
    ArrayList<Integer>[] adj;
    ArrayList<Integer>[] children;
    int[] size, color, coloring;
    long[] ans;
    TreeMap<Integer, Long> freq;

    public void dsuOnTree(int u, int p, boolean keep) {
        int bigChild = -1, max = 0;
        for (Integer v : adj[u]) {
            if (v != p && size[v] > max) {
                max = size[v];
                bigChild = v;
            }
        }
        for (Integer v : adj[u]) {
            if (v != p && v != bigChild) {
                dsuOnTree(v, u, false);
            }
        }
        if (bigChild != -1) {
            dsuOnTree(bigChild, u, true);
            children[u] = children[bigChild];
        }
        children[u].add(u);
        doColoring(u, false);
        for (Integer v : adj[u]) {
            if (v != p && v != bigChild) {
                for (Integer x : children[v]) {
                    doColoring(x, false);
                    children[u].add(x);
                }
            }
        }
        ans[u] = freq.lastEntry().getValue();
        if (!keep) {
            for (Integer v : children[u]) {
                doColoring(v, true);
            }
        }
    }

    public void doColoring(int u, boolean sub) {
        long x = freq.getOrDefault(coloring[color[u]], 0L);
        if (x - color[u] == 0) {
            freq.remove(coloring[color[u]]);
        } else {
            freq.put(coloring[color[u]], x - color[u]);
        }
        if (sub) {
            --coloring[color[u]];
        } else {
            ++coloring[color[u]];
        }
        x = freq.getOrDefault(coloring[color[u]], 0L);
        freq.put(coloring[color[u]], x + color[u]);
    }

    public void dfsSize(int u, int p) {
        size[u] = 1;
        for (Integer v : adj[u]) {
            if (v != p) {
                dfsSize(v, u);
                size[u] += size[v];
            }
        }
    }

    static class FastReader {

        StringTokenizer st;
        BufferedReader br;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) {
            try {
                br = new BufferedReader(new FileReader(s));
            } catch (Exception e) {
            }
        }

        public String next() {
            if (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public boolean hasNext() throws IOException {
            if (st != null && st.hasMoreTokens()) {
                return true;
            }
            String s = br.readLine();
            if (s == null || s.isEmpty()) {
                return false;
            }
            st = new StringTokenizer(s);
            return true;
        }
    }
}
