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.*;
import java.util.*;

public class LomsatGelral
{

	static ArrayList<Integer>[] tree;

	static int[] lo;
	static int[] hi;
	static int[] map;

	static int BLOCK;

	public static void main(String[] args){
		FS scan = new FS();
		PrintWriter out = new PrintWriter(System.out);
		int n = scan.nextInt();
		BLOCK = (int) Math.sqrt(n);
		int[] col = new int[n];
		tree = new ArrayList[n];
		for(int i = 0; i < n; i++) {
			col[i] = scan.nextInt();
			tree[i] = new ArrayList<Integer>();
		}
		for(int i = 0; i < n-1; i++) {
			int u = scan.nextInt()-1;
			int v = scan.nextInt()-1;
			tree[u].add(v);
			tree[v].add(u);
		}
		lo = new int[n];
		hi = new int[n];
		map = new int[n];
		coleman(0, -1);
		long[] ans = new long[n];
		Query[] qarr = new Query[n];
		for(int i = 0; i < n; i++) 
			qarr[i] = new Query(lo[i], hi[i], i);
		Arrays.sort(qarr);
		int best = 0;
		long[] sum = new long[100_002];
		int[] freq = new int[100_002];
		int moLeft = 0;
		int moRight = -1;
		for(int i = 0; i < n; i++) {
			Query q = qarr[i];
			while(moRight < q.r) {
				moRight++;
				int ele = map[moRight];
				int color = col[ele];
				freq[color]++;
				if(freq[color] > best) best = freq[color];
				sum[freq[color]] += color;
			}			
			while(moRight > q.r) {
				int ele = map[moRight];
				int color = col[ele];
				sum[freq[color]] -= color;
				if(sum[best] == 0) best = freq[color]-1;
				freq[color]--;
				moRight--;
			}
			while(moLeft > q.l) {
				moLeft--;
				int ele = map[moLeft];
				int color = col[ele];
				freq[color]++;
				if(freq[color] > best) best = freq[color];
				sum[freq[color]] += color;
			}
			while(moLeft < q.l) {
				int ele = map[moLeft];
				int color = col[ele];
				sum[freq[color]] -= color;
				if(sum[best] == 0) best = freq[color]-1;
				freq[color]--;
				moLeft++;
			}
			ans[q.i] = sum[best];
		}
		for(int i = 0; i < n; i++) out.print(ans[i]+" ");
		out.println();
		out.flush();
	}

	static int curr = 0;

	static void coleman(int root, int prev) {
		lo[root] = curr;
		map[curr] = root;
		for(int to : tree[root]) {
			if(to != prev) {
				curr++;
				coleman(to, root);
			}
		}
		hi[root] = curr;
	}

	static class Query implements Comparable<Query>{

		int l;
		int r;
		int i;

		public Query(int l, int r, int i) {
			this.l = l;
			this.r = r;
			this.i = i;
		}

		@Override
		public int compareTo(Query o)
		{
			if(l/BLOCK == o.l/BLOCK) return r-o.r;
			return l/BLOCK-o.l/BLOCK;
		}
	}

	static class FS {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		String next() {
			while(!st.hasMoreElements()) {
				try { st = new StringTokenizer(br.readLine()); }
				catch(Exception e) {}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
}