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
// Main Code at the Bottom
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.BigInteger; 
public class Main {
	//Fast IO class
    static class FastReader {
        BufferedReader br; 
        StringTokenizer st; 
        public FastReader() {
        	boolean env=System.getProperty("ONLINE_JUDGE") != null;
        	if(!env) {
        		try {
					br=new BufferedReader(new FileReader("src\\input.txt"));
				} catch (FileNotFoundException e) {
					e.printStackTrace();
				}
        	}
        	else br = new BufferedReader(new InputStreamReader(System.in)); 
        } 
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) {
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
        int nextInt() {
            return Integer.parseInt(next()); 
        } 
        long nextLong() {
            return Long.parseLong(next()); 
        } 
        double nextDouble() {
            return Double.parseDouble(next()); 
        } 
        String nextLine() {
            String str = ""; 
            try {
                str = br.readLine(); 
            } 
            catch (IOException e) {
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }     
    static long MOD=1000000000+7;
    //debug
    static void debug(Object... o) {
        System.out.println(Arrays.deepToString(o));
    }
    // Pair
    static class pair{
    	long x,y;
    	pair(long a,long b){
    		this.x=a;
    		this.y=b;
    	}
    	public boolean equals(Object obj) {
    		if(obj == null || obj.getClass()!= this.getClass()) return false;
            pair p = (pair) obj;
            return (this.x==p.x && this.y==p.y);
        }
    	public int hashCode() {
            return Objects.hash(x,y);
        }
    }
    static FastReader sc=new FastReader();
    static PrintWriter out=new PrintWriter(System.out);  
    //Global variables and functions
    static int V,color[],subtree_size[];
    static long ans[];
    static ArrayList<Integer> graph[];
    static void init(int n){
        V=n;
        graph=new ArrayList[V];
        subtree_size=new int[n];
        for(int i=0;i<V;i++) graph[i]=new ArrayList<>();
    }
    static void addEdge(int src,int dest){
        graph[src].add(dest);
        graph[dest].add(src);
    }
    static void dfs(int s,int p) {
    	subtree_size[s]=1;
    	for(Integer x: graph[s]) {
    		if(x==p) continue;
    		dfs(x,s);
    		subtree_size[s]+=subtree_size[x];
    	}
    }
    static void hld(int s,int p,HashMap<Integer,Integer> cur,TreeMap<Integer,Long> occ) {
    	int maxChild=-1,maxSize=-1;
    	for(Integer x: graph[s]) {
    		if(x==p) continue;
    		if(subtree_size[x]>maxSize) {
    			maxSize=subtree_size[x];
    			maxChild=x;
    		}
    	}
    	if(maxChild!=-1) hld(maxChild,s,cur,occ);
    	for(Integer x: graph[s]) {
    		if(x==p || x==maxChild) continue;
    		HashMap<Integer,Integer> tmp=new HashMap<>();
    		TreeMap<Integer,Long> tmp2=new TreeMap<>();
    		hld(x,s,tmp,tmp2);
    		for(Integer key: tmp.keySet()) {
    			if(cur.get(key)==null) {
    				cur.put(key,tmp.get(key));
    				occ.merge(tmp.get(key), (long)key, Long::sum);
    			}
    			else {
    				int val=cur.get(key);
    				cur.merge(key, tmp.get(key), Integer::sum);
    				occ.merge(val, (long)-key, Long::sum);
    				occ.merge(val+tmp.get(key), (long) key, Long::sum);
    			}
    		}
    	}
    	int key=color[s],val=1;
    	if(cur.get(key)==null) {
			cur.put(key,val);
			occ.merge(val, (long)key, Long::sum);
		}
		else {
			int v=cur.get(key);
			cur.merge(key, val, Integer::sum);
			occ.merge(v, (long)-key, Long::sum);
			occ.merge(v+val, (long) key, Long::sum);
		}
    	ans[s]=occ.get(occ.lastKey());
    }
    //Main function(The main code starts from here)
    public static void main (String[] args) throws java.lang.Exception {
    	int test=1;
    	//test=sc.nextInt();
    	while(test-->0){
    		int n=sc.nextInt();
    		init(n);
    		color=new int[n];
    		ans=new long[n];
    		for(int i=0;i<n;i++) color[i]=sc.nextInt();
    		for(int i=0;i<n-1;i++) addEdge(sc.nextInt()-1,sc.nextInt()-1);
    		dfs(0,-1);
    		hld(0,-1,new HashMap<>(),new TreeMap<>());
    		for(Long x: ans) out.print(x+" ");
    	}	
        out.flush();
        out.close();
    }
}