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.ArrayList;
import java.util.Scanner;
public class dsn  {
    static int n;
    static ArrayList<Integer>[] adj;
    static int[] father;
    static int[] son;
    static int[] size; // size of subtree;
    static boolean[] visited; // clear before every dfs
    static int cnt;
    static int[] code; //code of vertice
    static int[] color;
    static int[] color2; //coded
    static int[] rcode; //code of subtree
    
    static int[] time; //time of color i;
    static int mx; //max of time;
    static long[] sum; //sum of color of time;
    static long[] ans;
    public static void dfs1(int node)   {
        color2[cnt] = color[node];
        code[node] = cnt;
        cnt++;
        size[node] = 1;
        visited[node] = true;
        int mx = 0;
        int son0 = -1;
        for (int i: adj[node])   {
            if (!visited[i])   {
                father[i] = node;
                dfs1(i);
                size[node] += size[i];
                if (size[i] > mx)   {
                    son0 = i;
                    mx = size[i];
                }   
            }    
        }    
        rcode[node] = cnt - 1;
        son[node] = son0;
    }    
    public static void dsn(int node)   {
        if (node < 0) return;
        //destroy
        for (int i : adj[node])   {
            if (i != father[node] && i != son[node] && i > 0)   {
                dsn(i);
                mx = 0;
                for (int j = code[i]; j <= rcode[i]; j++)  {
                    sum[time[color2[j]]] = 0;
                    time[color2[j]] = 0;
                }    
            }    
        }    
        dsn(son[node]);
        //rebuild
        for (int i : adj[node])   {
            if (i != father[node] && i != son[node] && i > 0)   {
                for (int j = code[i]; j <= rcode[i]; j++)  {
                    sum[time[color2[j]]] -= color2[j];
                    time[color2[j]]++;
                    sum[time[color2[j]]] += color2[j];
                    if (time[color2[j]] > mx) mx = time[color2[j]];
                }    
            }    
        }
        sum[time[color[node]]] -= color[node];
        time[color[node]]++;
        sum[time[color[node]]] += color[node];
        if (time[color[node]] > mx) mx = time[color[node]];
        ans[node] = sum[mx];
    }    
    public static void main(String Args[])   {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        father = new int[n];
        son = new int[n];
        size = new int[n];
        visited = new boolean[n];
        cnt = 0;
        rcode = new int[n];
        color = new int[n];
        color2 = new int[n];
        code = new int[n];
        time = new int[n + 1]; //time of color i;
        mx = 0; //max of time;
        sum = new long[n]; //sum of color of time;
        ans = new long[n];
        adj = (ArrayList<Integer>[]) new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) color[i] = sc.nextInt();
        for (int i = 0; i < n- 1; i++)   {
            int x = sc.nextInt()-1;
            int y = sc.nextInt()-1;
            adj[x].add(y);
            adj[y].add(x);
        }    
        dfs1(0);
        dsn(0);
        StringBuilder answer = new StringBuilder();
        for (int i = 0; i < n; i++) {
            answer.append(ans[i]);
            answer.append(" ");
        }        
        System.out.println(answer);
    }    
}    