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 CF {
	
     public static void main(String[] args) {
       
         InputStream instream = System.in;
         OutputStream outstream = System.out;
         Scanner in = new Scanner(instream);
         PrintWriter out = new PrintWriter(outstream);
	     new solve().slv(in,out);
	     out.close(); 
      }
}


class solve{
	
	long ans[] ;
	int col[] ;
	public void slv(Scanner in , PrintWriter out){
		 int n = in.nextInt();
		 ans = new long[n];
		 col = new int[n];
		 for(int i=0;i<n ; i++){
			 col[i] = in.nextInt();
		 }
		 Tree tr = new Tree(n , col);
		 int from , to ;
		 for(int i=0 ; i<n-1 ; i++){
			 from = in.nextInt();
			 to   = in.nextInt();
			 tr.add_edge(from-1, to-1);
		 }
		 dfs(tr.r , new boolean[n]);
		 for(long i:ans){
			 out.print(i + " ");
		 }
	}
	
	Query dfs(Nd n , boolean[] arr){
		arr[n.iNdx] = true ;
		Query q = new Query();
		q.add_col(n.color, 1);
		for(Nd nd : n.connection.values()){
			  if(arr[nd.iNdx]) continue ;
			  Query chld = dfs(nd , arr);
			  if(chld.sbt_col.size() > q.sbt_col.size()){
				  q = chld.combine(q);
			  }
			  else {
				  q = q.combine(chld);
			  }
			  
		}
		ans[n.iNdx] = q.ans ;
		return q ;
	}

}
class Query{
	
	Map<Integer, Integer> sbt_col = new HashMap<>();
	long max = 0 , ans = 0 ;
	
	public void add_col(int k , int v){
		if(sbt_col.containsKey(k)) sbt_col.put(k , v+sbt_col.get(k));
		else sbt_col.put(k, v);
		
		int check = sbt_col.get(k);
		if(check > max){
			max= check ;
			ans = k ;
		}else if(check == max) ans += k ;
	}
	
	Query combine(Query obj){
		for (Map.Entry<Integer, Integer> e : obj.sbt_col.entrySet()) {
            add_col(e.getKey(), e.getValue());
        }
		return this ;
	}
	
}

class Nd{
	int iNdx ;
	int color ;
	Map<Integer, Nd> connection = new HashMap<>();
	public Nd(int i , int c){
		iNdx = i;
		color = c ;
	}
	
	
}
class Tree {
	 
	Nd Nds[] ;
    Nd r ;
	
    public Tree(int n , int[] col){
    	Nds = new Nd[n] ;
    	for(int i=0 ; i<n; i++){
    		Nds[i] = new Nd(i,col[i]);
    	}
    	r = Nds[0];
    }
    
    public void add_edge(int from , int to){
    	Nds[from].connection.put(to , Nds[to]);
    	Nds[to].connection.put(from , Nds[from]);
    }
}