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

public class LomsatGelral {
	
	static int[] colors;
	static ArrayList<Integer>[] edges;
	static TreeMap<Integer, Integer>[] ctoO;
	//static TreeSet<Pair>[] o;
	static long[] ans;
	static int[] max;
	//static boolean[] vis;
	public static void main(String[] args) throws Exception{
		BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(f.readLine());
		
		colors = new int[n];
		edges = new ArrayList[n];
		//o = new TreeSet[n];
		ctoO = new TreeMap[n];
		ans = new long[n];
		max = new int[n];
		//vis = new boolean[n];
		for(int i = 0;i<n;i++) {
			edges[i] = new ArrayList<Integer>();
			ctoO[i] = new TreeMap<Integer,Integer>();
			//o[i] = new TreeSet<Pair>();
		}
		
		StringTokenizer st = new StringTokenizer(f.readLine());
		for(int i = 0;i<n;i++) {
			colors[i] = Integer.parseInt(st.nextToken());
		}
		
		for(int i = 0;i<n-1;i++) {
			st = new StringTokenizer(f.readLine());
			int x = Integer.parseInt(st.nextToken()) - 1;
			int y = Integer.parseInt(st.nextToken()) - 1;
			edges[x].add(y);
			edges[y].add(x);
		}
		
		dfs(0,-1);
		
		for(int i = 0;i<n;i++) {
			System.out.print(ans[i] + " ");
		}
	}
	
	public static void dfs(int x, int p) {
		
		if(edges[x].size() == 1 && x != 0) {
			//o[x].add(new Pair(colors[x],1));
			ctoO[x].put(colors[x], 1);
			ans[x] = colors[x];
			max[x] = 1;
			return;
		}
		
		int maxI = -1;
		int maxSize = -1;
		for(int e: edges[x]) {
			if(e != p) {
				dfs(e, x);
				if(ctoO[e].size() > maxSize) {
					maxI = e;
					maxSize = ctoO[e].size();
				}
			}
		}
		
		ctoO[x] = ctoO[maxI];
		//o[x] = o[maxI];
		max[x] = max[maxI];
		ans[x] = ans[maxI];
		
		int size = 1;
		if(ctoO[x].containsKey(colors[x])) {
			ctoO[x].put(colors[x], 1 + ctoO[x].get(colors[x]));
			//o[x].add(new Pair(colors[x],ctoO[x].get(colors[x])));
			
			size = ctoO[x].get(colors[x]);
		}
		else {
			ctoO[x].put(colors[x], 1);
			//o[x].add(new Pair(colors[x],1));
		}
		
		if(size == max[x]) {
			ans[x] += colors[x];
		}
		else if(size > max[x]) {
			ans[x] = colors[x];
			max[x] = size;
		}
		
		for(int e:edges[x]) {
			if(e != p && e != maxI) {
				while(ctoO[e].size() > 0) {
					int c = ctoO[e].firstKey();
					int occ = ctoO[e].get(c);
					size = occ;
					ctoO[e].remove(c);
					if(ctoO[x].containsKey(c)) {
						ctoO[x].put(c, occ + ctoO[x].get(c));
						//o[x].add(new Pair(c,ctoO[x].get(c)));
						
						size = ctoO[x].get(c);
					}
					else {
						ctoO[x].put(c, occ);
						//o[x].add(new Pair(c,occ));
					}
					
					if(size == max[x]) {
						ans[x] += c;
					}
					else if(size > max[x]) {
						ans[x] = c;
						max[x] = size;
					}
				}
			}
		}
		
		
		
	}
	
	static class Pair implements Comparable<Pair>{
		int color;
		int occurences = 0;
		Pair(int color, int occurences){
			this.color = color;
			this.occurences = occurences;
		}
		@Override
		public int compareTo(Pair arg0) {
			return occurences - arg0.occurences;
		}
	}

}
