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.util.*;
import java.lang.*;
import java.io.*;

public class Main {

    static int n;
    static int[] dp;
    static boolean[] v;
    static ArrayList<HashMap<Integer, Integer>> m;
    static ArrayList<ArrayList<Integer>> g;
    static long[] res, sum;

    static void DFS(int s, int p) {
        int sz = 1;
        int szi = s;
        for (int i = 0; i < g.get(s).size(); i++) {
            if (g.get(s).get(i) != p) {
                DFS(g.get(s).get(i), s);
                if (m.get(g.get(s).get(i)).size() > sz) {
                    sz = m.get(g.get(s).get(i)).size();
                    szi = g.get(s).get(i);
                }
            }
        }
        HashMap<Integer, Integer> tempm = m.get(s);
        m.set(s, m.get(szi));
        m.set(szi, tempm);
        dp[s] = dp[szi];
        dp[szi] = 1;
        long temp = sum[s];
        sum[s] = sum[szi];
        sum[szi] = temp;
        for (int i = 0; i < g.get(s).size(); i++) {
            if (g.get(s).get(i) != p) {
                for (Map.Entry<Integer, Integer> entry : m.get(g.get(s).get(i)).entrySet()) {
                    if (m.get(s).get(entry.getKey()) == null) {
                        m.get(s).put(entry.getKey(), entry.getValue());
                    } else {
                        m.get(s).put(entry.getKey(), entry.getValue() + m.get(s).get(entry.getKey()));
                    }
                    if (dp[s] < m.get(s).get(entry.getKey())) {
                        dp[s] = m.get(s).get(entry.getKey());
                        sum[s] = entry.getKey();
                    } else if (dp[s] == m.get(s).get(entry.getKey())) {
                        sum[s] += entry.getKey();
                    }
                }
                m.get(g.get(s).get(i)).clear();
                g.get(g.get(s).get(i)).clear();
            }
        }
        res[s] = sum[s];
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        String[] ar;
        StringBuilder sb = new StringBuilder();
        //-----------------------------------------------------------------------
        n = Integer.parseInt(br.readLine());
        dp = new int[n];
        g = new ArrayList();
        v = new boolean[n];
        res = new long[n];
        sum = new long[n];
        m = new ArrayList();
        ar = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(ar[i]);
            g.add(new ArrayList());
            m.add(new HashMap());
            m.get(i).put(x, 1);
            res[i] = x;
            sum[i] = x;
            dp[i] = 1;
        }
        for (int i = 0; i < n - 1; i++) {
            ar = br.readLine().split(" ");
            int x = Integer.parseInt(ar[0]) - 1;
            int y = Integer.parseInt(ar[1]) - 1;
            g.get(x).add(y);
            g.get(y).add(x);
        }
        DFS(0, -1);
        for (int i = 0; i < n; i++) {
            sb.append(res[i] + " ");
        }
        //-----------------------------------------------------------------------
        System.out.println(sb);
    }
}
