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.TreeMap;
import java.util.StringTokenizer;
import java.util.Map.Entry;

public class E {
	static int n, color[];
	static long ans[];
	static ArrayList<Integer> adj[];
	static boolean[] vis;

	static int node, maxx1;
	static long anss1;

	static TreeMap<Integer, Integer> dfs(int u, int parent) {
		vis[u] = true;
		TreeMap<Integer, Integer> max = new TreeMap<>();
		long anss = 0;
		int maxx = -1;
		for (int v : adj[u]) {
			if (v != parent) {
				TreeMap<Integer, Integer> in = dfs(v, u);
				if (in.size() > max.size()) {
					TreeMap<Integer, Integer> tmp = in;
					in = max;
					max = tmp;
					if (v == node) // get the answer of the larger subtree to
									// yourself, in order to acculmulate on it
					{
						anss = anss1;
						maxx = maxx1;
					}
				}
				for (Entry<Integer, Integer> entry : in.entrySet()) {
					int val = entry.getValue();
					int key = entry.getKey();
					if (max.get(key) == null) {
						max.put(key, val);
					}
					else {
						val = max.get(key) + val;
						max.put(key, val);
					}
					if (val > maxx) {
						maxx = val;
						anss = key;
					}
					else
						if (val == maxx)
							anss += key;
				}
			}
		}
		if (!max.containsKey(color[u]))
			max.put(color[u], 1);
		else
			max.put(color[u], max.get(color[u]) + 1);
		int val = max.get(color[u]);
		if (val > maxx) {
			maxx = val;
			anss = color[u];
		}
		else
			if (val == maxx)
				anss += color[u];
		{
			node = u;
			maxx1 = maxx;
			anss1 = anss;
		}
		ans[u] = anss;
		return max;
	}

	@SuppressWarnings("unchecked")
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);

		n = sc.nextInt();
		color = new int[n];
		for (int i = 0; i < n; i++)
			color[i] = sc.nextInt();
		ans = new long[n];
		vis = new boolean[n];
		adj = new ArrayList[n];
		for (int i = 0; i < n; i++)
			adj[i] = new ArrayList<>();
		for (int i = 0; i < n - 1; i++) {
			int u = sc.nextInt() - 1;
			int v = sc.nextInt() - 1;
			adj[u].add(v);
			adj[v].add(u);
		}
		dfs(0, -1);
		for (long x : ans)
			pw.print(x + " ");
		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();
		}
	}
}
