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.*;
public class lomsat {
	public static boolean[] visited;
	public static int[] answers;
	public static long[] maxvals;
	public static long[] maxidxs;
	public static HashMap<Integer, Integer> dfs(int node, int[] arr, ArrayList<Integer>[] adj) {
		visited[node] = true;
		HashMap<Integer, Integer> curr = new HashMap<Integer, Integer> ();
		curr.put(arr[node], 1);
		maxvals[node] = 1;
		maxidxs[node] = arr[node];
		for(int i = 0; i < adj[node].size(); i++) {
			if(visited[adj[node].get(i)])continue;
			HashMap<Integer, Integer> arr2 = dfs(adj[node].get(i), arr, adj);
			if (arr2.size() > curr.size()) {
                HashMap<Integer, Integer> tmp = curr;
                curr = arr2;
                arr2 = tmp;
                maxvals[node] = maxvals[adj[node].get(i)];
                maxidxs[node] = maxidxs[adj[node].get(i)];
            }
            for (int c : arr2.keySet()) {
                curr.put(c, curr.getOrDefault(c, 0) + arr2.get(c));
                if (curr.get(c) > maxvals[node]) {
                    maxvals[node] = curr.get(c);
                    maxidxs[node] = c;
                } else if (curr.get(c) == maxvals[node]) {
                    maxidxs[node] += c;
                }
            }
		}		
		return curr;
	}
	
	public static void main(String[] args) {
		
		Scanner x = new Scanner(System.in);
		int n = x.nextInt();
		maxvals = new long[n+1];
		maxidxs = new long[n+1];
		visited = new boolean[n+1];
		answers = new int[n+1];
		int[] arr = new int[n+1];
		for(int i = 1; i <= n; i++)arr[i] = x.nextInt();
		ArrayList<Integer>[] adj = new ArrayList[n+1];
		for(int i = 0; i <= n; i++)adj[i] = new ArrayList<Integer>();
		for(int i = 0; i < n-1; i++) {
			int a = x.nextInt();
			int b = x.nextInt();
			adj[a].add(b);
			adj[b].add(a);
		}
		dfs(1, arr, adj);
		for(int i = 1; i <= n; i++) {
			System.out.println(maxidxs[i]);
		}
	}
}

class NumPair implements Comparable<NumPair>{
	int num, val;
	
	public NumPair(int a, int b) {
		num = a;
		val = b;
	}
	public int compareTo(NumPair other) {
		if (this.num == other.num)return 0;
		else return (this.val - other.val == 0 ? this.val-other.val:this.num-other.num);
	}
	public String toString() {
		return num + " " + val;
	}
}
