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.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;

public class Lomsatgelral {

	public static int color[];
	public static ArrayList<Integer> graph[];
	public static long ans[];
	public static int high[];
	public static HashMap<Integer, Integer> mp[];

	public static void insert(int x, int color, int num) {
		int add = num;
		if (mp[x].containsKey(color)) {
			add = mp[x].get(color) + num;
		}
		mp[x].put(color, add);
		if (add > high[x]) {
			ans[x] = color;
			high[x] = add;
		} else if (add == high[x]) {
			ans[x] += color;
		}
		return;
	}

	public static void dfs(int node, int p) {

		for (int i = 0; i < graph[node].size(); i++) {
			if (graph[node].get(i) == p)
				continue;
			dfs(graph[node].get(i), node);
		}

		int large = -1;
		int h = -2;
		for (int i = 0; i < graph[node].size(); i++) {
			if (graph[node].get(i) == p)
				continue;
			if (mp[graph[node].get(i)].size() > large) {
				large = mp[graph[node].get(i)].size();
				h = graph[node].get(i);
			}
		}
		//System.out.println(large + " " + (h + 1) + " " + (node + 1));
		if (h != -2) {
			mp[node] = mp[h];
			high[node] = high[h];
			ans[node] = ans[h];

			for (int i = 0; i < graph[node].size(); i++) {
				if (graph[node].get(i) == p || graph[node].get(i) == h)
					continue;
				int n2 = graph[node].get(i);

				for (int j : mp[n2].keySet()) {
					int freq = mp[n2].get(j);
					insert(node, j, freq);
				}

			}

		}

		insert(node, color[node], 1);

	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

		
		int n = Integer.parseInt(in.readLine());
		color = new int[n];
		graph = new ArrayList[n];
		mp = new HashMap[n];
		high=new int[n];
		ans=new long[n];
		for (int i = 0; i < n; i++) {
			graph[i] = new ArrayList();
			mp[i] = new HashMap();
		}
		String[] y = in.readLine().split(" ");
		for (int i = 0; i < n; i++) {
			color[i] = Integer.parseInt(y[i]);
		}

		for (int i = 0; i < n - 1; i++) {
			y = in.readLine().split(" ");
			int one = Integer.parseInt(y[0]) - 1;
			int two = Integer.parseInt(y[1]) - 1;
			graph[one].add(two);
			graph[two].add(one);
		}

		dfs(0, -1);
		for (int i = 0; i < n; i++) {
			out.print(ans[i]+" ");
		}
		out.print("\n");
		
		out.close();

	}
}
