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 static java.lang.Math.*;
import static java.util.Arrays.*;

import java.util.*;
import java.io.*;

public class Main {

	void solve() {
		int n = sc.nextInt();
		V[] vs = new V[n];
		for (int i = 0; i < n; i++) {
			V v = new V(i+1);
			v.color = sc.nextInt();
			vs[i] = v;
			v.s.add(pii(1, v.color));
			v.t.put(v.color, 1);
			v.maxCount = 1;
			v.sdc = v.color;
		}
		for (int i = 0; i < n - 1; i++) {
			int x = sc.nextInt() - 1;
			int y = sc.nextInt() - 1;
			vs[x].add(vs[y]);
			vs[y].add(vs[x]);
		}
		ans = new long[n];
		dfs(vs[0], null);
		ans[0] = vs[0].sdc;
		print(ans);
	}
	long[] ans;
		
	void dfs(V cur, V prev) {
		for (V child : cur) if (child != prev) {
			dfs(child, cur);
			ans[child.id-1] = child.sdc;
			merge(cur, child);
		}
	}
	
	void merge(V large, V small) {
		if (large.s.size() < small.s.size()) {
			merge(small, large);
			large.s = small.s;
			large.t = small.t;
			large.maxCount = small.maxCount;
			large.sdc = small.sdc;
			return;
		}
		for (int color : small.t.keySet()) {
			int oldValue = large.t.getOrDefault(color, 0);
			int newValue = small.t.get(color) + oldValue;
			large.t.put(color, newValue);
			if (oldValue > 0) large.s.remove(pii(oldValue, color));
			large.s.add(pii(newValue, color));
			
			if (large.maxCount < newValue) {
				large.maxCount = newValue;
				large.sdc = color;
			} else if (large.maxCount == newValue) {
				large.sdc += color;
			}
		}
	}
	
	static long pii(int a, int b) {
		return ((long)a << 32) + b;
	}
	
	class V extends ArrayList<V> {
		int id;
		int color;
		V(int id) { this.id = id; }
		int maxCount = 0;
		long sdc; // sums of dominating colours
		TreeSet<Long> s = new TreeSet<>(new ReverseOrder()); // <count, color>
		Map<Integer, Integer> t = new HashMap<>(); // <color, count>
	}
	
	class ReverseOrder implements Comparator<Long> {
		@Override
		public int compare(Long a, Long b) {
			return -Long.compare(a, b);
		}
	}
	
	static void tr(Object... os) { System.err.println(deepToString(os)); }
	static void tr(int[][] as) { for (int[] a : as) tr(a); }

	void print(long[] a) {
		out.print(a[0]);
		for (int i = 1; i < a.length; i++) out.print(" " + a[i]);
		out.println();
	}

	public static void main(String[] args) throws Exception {
		new Main().run();
	}

	MyScanner sc = null;
	PrintWriter out = null;
	public void run() throws Exception {
		sc = new MyScanner(System.in);
		out = new PrintWriter(System.out);
		for (;sc.hasNext();) {
			solve();
			out.flush();
		}
		out.close();
	}

	class MyScanner {
		String line;
		BufferedReader reader;
		StringTokenizer tokenizer;

		public MyScanner(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}
		public void eat() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					line = reader.readLine();
					if (line == null) {
						tokenizer = null;
						return;
					}
					tokenizer = new StringTokenizer(line);
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
		}
		public String next() {
			eat();
			return tokenizer.nextToken();
		}
		public String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		public boolean hasNext() {
			eat();
			return (tokenizer != null && tokenizer.hasMoreElements());
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}
	}
}