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.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
import java.util.function.BiFunction;

public class E600 {

    static BufferedReader br;
    static StringTokenizer st;
    static PrintWriter pw;

    static String nextToken() {
        try {
            while (st == null || !st.hasMoreTokens()) {
                st = new StringTokenizer(br.readLine());
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
        return st.nextToken();
    }

    static int nextInt() {
        return Integer.parseInt(nextToken());
    }

    public static void main(String[] args) {
        br = new BufferedReader(new InputStreamReader(System.in));
        pw = new PrintWriter(System.out);
        solve();
        pw.close();
    }

    static int[] color;
    static int n;


    static int[] edges;
    static int[] head;
    static int[] next;
    static int id = 0;

    private static void solve() {
        n = nextInt();
        color = new int[n];
        for (int i = 0; i < n; i++) {
            color[i] = nextInt();
        }
        edges = new int[n * 2];
        next = new int[n * 2];
        head = new int[n];
        Arrays.fill(head, -1);
        for (int i = 0; i < n - 1; i++) {
            int x = nextInt() - 1;
            int y = nextInt() - 1;
            addEdge(x, y);
            addEdge(y, x);
        }
        used = new boolean[n];
        pairs = new Pair[n];
        dfs(0);
        for (Pair p :
                pairs) {
            pw.print(p.ans);
            pw.print(" ");
        }
    }

    static boolean used[];
    static Pair[] pairs;

    private static HashMap<Integer, Integer> dfs(int v) {
        used[v] = true;
        HashMap<Integer, Integer> ans = new HashMap<>();
        ans.put(color[v], 1);
        ArrayList<HashMap<Integer, Integer>> maps = new ArrayList<>();
        long ansLong = color[v];
        int max = 1;
        for (int i = head[v]; i != -1; i = next[i]) {
            int vv = edges[i];
            if (used[vv]) continue;
            HashMap<Integer, Integer> map1 = dfs(vv);
            if (ans.size() < map1.size()) {
                HashMap c = map1;
                map1 = ans;
                ans = c;
                ansLong = pairs[vv].ans;
                max = pairs[vv].max;
            }
            maps.add(map1);
        }
        HashSet<Integer> was = new HashSet<>();

        for (HashMap<Integer, Integer> map : maps) {
            for (Map.Entry<Integer, Integer> entry :
                    map.entrySet()) {
                if (!ans.containsKey(entry.getKey())) {
                    ans.put(entry.getKey(), 0);
                }
                ans.merge(entry.getKey(), entry.getValue(), Integer::sum);
                int kk = ans.get(entry.getKey());
                if (kk == max && !was.contains(entry.getKey())) {
                    ansLong += entry.getKey();
                    was.add(entry.getKey());
                } else if (kk > max) {
                    max = kk;
                    ansLong = entry.getKey();
                    was.clear();
                    was.add(entry.getKey());
                }
            }
        }
        pairs[v] = new Pair(ansLong, max);
        return ans;
    }

    private static void addEdge(int x, int y) {
        edges[id] = y;
        next[id] = head[x];
        head[x] = id++;
    }
}

class Pair {
    long ans;
    int max;

    public Pair(long ans, int max) {
        this.ans = ans;
        this.max = max;
    }
}