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.*;
import java.util.Map.Entry;
public class CF600_D12_E{
	public static void main(String[] args)throws Throwable {
		MyScanner sc=new MyScanner();
		PrintWriter pw=new PrintWriter(System.out);
		
		n=sc.nextInt();
		col=new int [n];
		for(int i=0;i<n;i++)
			col[i]=sc.nextInt();
		adj=new ArrayList [n];
		for(int i=0;i<n;i++)
			adj[i]=new ArrayList<Integer>();
		for(int i=0;i<n-1;i++){
			int u=sc.nextInt()-1;
			int v=sc.nextInt()-1;
			adj[u].add(v);
			adj[v].add(u);
		}
		maxCnt=new int [n];
		maxSum=new long [n];
		sz=new int [n];
		map=new HashMap [n];
		dfs1(0, -1);
		dfs(0, -1);
		for(long x : maxSum)
			pw.print(x+" ");
		pw.flush();
		pw.close();
	}
	
	static int n;
	static int [] col,sz;
	static long [] ans;
	static ArrayList<Integer> [] adj;
	static HashMap<Integer, Integer> [] map;
	static int [] maxCnt;
	static long [] maxSum;
	
	static int dfs1(int u,int p){
		int ret=1;
		for(int v : adj[u])
			if(v!=p)
				ret+=dfs1(v, u);
		return sz[u]=ret;
	}
	
	static void dfs(int u,int p){
		int max=-1,bigChild=-1;
		for(int v : adj[u])
			if(v!=p){
				dfs(v, u);
				if(sz[v]>max){
					max=sz[v];
					bigChild=v;
				}
			}
		if(bigChild==-1){
			maxCnt[u]=0;
			maxSum[u]=0;
			map[u]=new HashMap<Integer, Integer>();
		}
		else{
			maxCnt[u]=maxCnt[bigChild];
			maxSum[u]=maxSum[bigChild];
			map[u]=map[bigChild];
		}
		int occ=map[u].getOrDefault(col[u], 0);
		map[u].put(col[u], ++occ);
		if(occ==maxCnt[u])
			maxSum[u]+=col[u];
		else
			if(occ>maxCnt[u]){
				maxCnt[u]=occ;
				maxSum[u]=col[u];
			}
		for(int v : adj[u])
			if(v!=p && v!=bigChild)
				for(Entry<Integer, Integer> e : map[v].entrySet()){
					occ=map[u].getOrDefault(e.getKey(), 0)+e.getValue();
					map[u].put(e.getKey(), occ);
					if(occ==maxCnt[u])
						maxSum[u]+=e.getKey();
					else
						if(occ>maxCnt[u]){
							maxCnt[u]=occ;
							maxSum[u]=e.getKey();
						}
				}
	}
	
	static class MyScanner {
		BufferedReader br;
		StringTokenizer st;
		public MyScanner() {
			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;}
	}
} 