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.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.StringTokenizer;

public class LomsatGerlal {
	static int color[];
	static ArrayList<Integer> adj[];
	static int[] sumSubTree;
	static HashMap<Integer, Integer> ans[];

	// static void dfs(int u, int p) {
	//
	// int ans = 1;
	// for (int v : adj[u])
	// if (v != p) {
	// dfs(v, u);
	// ans += sumSubTree[v];
	// }
	// sumSubTree[u] = ans;
	// }
	static long[] max, sum;

	static void solve(int u, int p) {

		int mx = -1, szMax = -1;
		for (int v : adj[u])
			if (v != p) {
				solve(v, u);
				if (ans[v].size() > szMax) {
					szMax = ans[v].size();
					mx = v;
				}
			}
		HashMap<Integer, Integer> mine;
		long max2, sum2;
		if (mx != -1) {
			mine = ans[mx];
			max2 = max[mx];
			sum2 = sum[mx];
		}
		else {
			mine = new HashMap<>();
			max2 = 0;
			sum2 = 0;
		}
		Integer cc = mine.get(color[u]);
		if (cc != null) {
			mine.put(color[u], cc + 1);
			if (cc + 1 == max2) {
				sum2+=color[u];
			}
			else
				if (cc + 1 > max2) {
					max2 = cc + 1;
					sum2 = color[u];
				}
		}
		else {
			mine.put(color[u], 1);
			cc = 0;
			if (cc + 1 == max2) {
				sum2+=color[u];
			}
			else
				if (cc + 1 > max2) {
					max2 = cc + 1;
					sum2 = color[u];
				}
		}

		for (int v : adj[u])
			if (v != p && v != mx) {
//				System.out.println(u + "  " + sum2);
				for(Entry<Integer, Integer> entry : ans[v].entrySet()){
					int col = entry.getKey();
					int val = entry.getValue();
					cc = mine.get(col);
					if (cc != null) {
						mine.put(col, cc + val);
						if (cc + val == max2) {
							sum2+=col;
						}
						else
							if (cc + val > max2) {
								max2 = cc + val;
								sum2 = col;
							}
					}
					else {
						mine.put(col, val);
						cc = 0;
						if (cc + val == max2) {
							sum2+=col;
						}
						else
							if (cc + val > max2) {
								max2 = cc + val;
								sum2 = col;
							}
					}
				}
			}
		max[u] = max2;
		sum[u] = sum2;
		ans[u] = mine;

	}

	@SuppressWarnings("unchecked")
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		color = new int[n];
		for (int i = 0; i < n; i++)
			color[i] = sc.nextInt();

		adj = new ArrayList[n];
		for (int i = 0; i < n; i++)
			adj[i] = new ArrayList<>();

		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);
		}

		sumSubTree = new int[n];
		// dfs(0, -1);
		ans = new HashMap[n];
		max = new long[n];
		sum = new long[n];
		solve(0, -1);
		PrintWriter pw = new PrintWriter(System.out);
		for(long v : sum)
			pw.print(v + " ");
		pw.println();
		pw.flush();
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(String s) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(new File(s)));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public boolean ready() throws IOException {
			return br.ready();
		}
	}
}
