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 A{

	static long []ans;
	static ArrayList<Integer> []adj;
	static HashMap<Integer,Integer>[]maps;
	static int []col,maxOcc;
	static long[] merge(int small,int big,long ret,int max) {
		
		for(int x:maps[small].keySet()) {
			int newOcc=maps[big].getOrDefault(x, 0)+maps[small].get(x);
			maps[big].put(x,newOcc);
			if(newOcc==max) {
				ret+=x;
			}
				
			else if(newOcc>max) {
				ret=x;
				max=newOcc;
			}
		}
		
		
		return new long[] {ret,max};
	}
	static void dfs(int u,int p) {
		boolean leaf=true;
		for(int v:adj[u])
			if(v!=p) {
				dfs(v,u);
				leaf=false;
			}
		if(leaf) {
			maps[u]=new HashMap();
			maps[u].put(col[u], 1);
			ans[u]=col[u];
			maxOcc[u]=1;
			return;
		}
		
	
		maps[u]=new HashMap();
		long ret=col[u];
		maps[u].put(col[u],1);
		int max=1;
		
		for(int v:adj[u])
			if(v!=p) {
				if(maps[u].size()<maps[v].size()) {
					
					long []tmp=merge(u, v, ans[v],maxOcc[v]);
					ret=tmp[0];
					max=(int)tmp[1];
					
					maps[u]=maps[v];
				}
				else
				{
					long []tmp=merge(v, u, ret,max);
					
					ret=tmp[0];
					max=(int)tmp[1];
					
					
				}
			}
		
		ans[u]=ret;
		maxOcc[u]=max;
		
	}
	public static void main(String[] args) throws IOException {
		Scanner sc=new Scanner();
		PrintWriter out=new PrintWriter(System.out);
		int n=sc.nextInt();
		col=new int [n];
		maxOcc=new int [n];
		adj=new ArrayList[n];
		maps=new HashMap[n];
		for(int i=0;i<n;i++) {
			col[i]=sc.nextInt();
			adj[i]=new ArrayList();
			
		}
		ans=new long [n];
		for(int i=1;i<n;i++) {
			int u=sc.nextInt()-1,v=sc.nextInt()-1;
			adj[u].add(v);
			adj[v].add(u);
		}
		dfs(0, -1);
		for(long x:ans)
			out.println(x);
		out.close();

	}
	static class Scanner
	{
		BufferedReader br;
		StringTokenizer st;
		Scanner(){
			br=new BufferedReader(new InputStreamReader(System.in));
		}
		Scanner(String fileName) throws FileNotFoundException{
			br=new BufferedReader(new FileReader(fileName));
		}
		String next() throws IOException {
			while(st==null || !st.hasMoreTokens())
				st=new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		String nextLine() throws IOException {
			return br.readLine();
		}
		int nextInt() throws IOException{
			return Integer.parseInt(next());
		}
		long nextLong()  throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}
		double nextDouble() throws NumberFormatException, IOException {
			return Double.parseDouble(next());
		}
	}
}