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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.HashMap;
import java.util.HashSet;

public class LomsatGelral {
	public static void main(String[] args) {
		Kattio io = new Kattio(System.in,System.out);
		Solve solve = new Solve(io);
		solve.main();
		io.close();
	}
}

class Pair<X,Y>
{
	X x;
	Y y;
	Pair(X x,Y y)
	{
		this.x = x;
		this.y = y;
	}
	
	@Override
	public String toString()
	{
		return "["+x.toString()+","+y.toString()+"]";
	}
}

class Solve
{
	Kattio io;
	int n;
	int[] c;
	
	ArrayList<ArrayList<Integer>> V;
	
	int[] res;
	long[] sum;
	
	boolean[] visited;
	
	ArrayList<Map<Integer,Set<Integer>>> M; // occurrence, set of color
	ArrayList<Map<Integer,Integer>> S; // color, occurrence
	
	int currentRes;
	long currentSum;
	
	public Solve(Kattio io)
	{
		this.io = io;
	}
	
	private void addColor(Map<Integer,Integer> currentS,Map<Integer,Set<Integer>> currentM,int color,int occurrence)
	{
		if (currentS.containsKey(color))
		{
			int currentOccurrence = currentS.get(color);
			currentS.remove(color);
			currentS.put(color,currentOccurrence+occurrence);
			currentM.get(currentOccurrence).remove(color);
			if (!currentM.containsKey(currentOccurrence+occurrence))
				currentM.put(currentOccurrence+occurrence,new HashSet<>());
			
			currentM.get(currentOccurrence+occurrence).add(color);
			if (currentOccurrence+occurrence>currentRes)
			{
				currentRes = currentOccurrence+occurrence;
				currentSum = color;
			}
			else
			if (currentOccurrence+occurrence==currentRes)
				currentSum+=(long) color;
		}
		else
		{
			int currentOccurrence = 0;
			currentS.put(color,occurrence);
			if (!currentM.containsKey(occurrence))
				currentM.put(occurrence, new HashSet<>());
			
			currentM.get(occurrence).add(color);
			
			if (currentOccurrence+occurrence>currentRes)
			{
				currentRes = currentOccurrence+occurrence;
				currentSum = color;
			}
			else
			if (currentOccurrence+occurrence==currentRes)
				currentSum+=(long) color;
		}
	}
	
	private void dfs(int x)
	{
		visited[x] = true;
		
		ArrayList<Pair<Integer,Integer>> A = new ArrayList<>();
		
		for (int y: V.get(x))
		if (!visited[y])
		{
			dfs(y);
			A.add(new Pair<>(y,S.get(y).size()));
		}
		
		Collections.sort(A,(a,b)->{
			return b.y-a.y;
		});
		
		//io.println(A);
		
		Map<Integer,Set<Integer>> currentM;
		Map<Integer,Integer> currentS;
		
		if (A.size()==0)
		{
			currentM = new HashMap<>();
			currentS = new HashMap<>();
			currentRes = 0;
			currentSum = 0;
		}
		else
		{
			currentM = M.get(A.get(0).x);
			currentS = S.get(A.get(0).x);
			currentRes = res[A.get(0).x];
			currentSum = sum[A.get(0).x];
			
			for (int i=1; i<A.size(); i++)
			{
				for (Map.Entry<Integer,Integer> entry: S.get(A.get(i).x).entrySet())
				{
					int color = entry.getKey();
					int occurrence = entry.getValue();
					
					addColor(currentS,currentM,color,occurrence);
				}
			}	
		}
		
		int color = c[x];
		int occurrence = 1;
		addColor(currentS,currentM,color,occurrence);
		
		//io.println(x+" "+currentS+" "+currentM+" "+color+" "+occurrence+" "+currentRes+" "+currentSum);
		
		S.set(x,currentS);
		M.set(x,currentM);
		res[x] = currentRes;
		sum[x] = currentSum; 
	}
	
	public void main()
	{
		n = io.getInt();
		c = new int[n+1];
		for (int i=1; i<=n; i++)
			c[i] = io.getInt();
		
		V = new ArrayList<>();
		for (int i=0; i<=n; i++)
			V.add(new ArrayList<>());
		
		for (int i=1; i<n; i++)
		{
			int u,v;
			u = io.getInt();
			v = io.getInt();
			V.get(u).add(v);
			V.get(v).add(u);
		}
		
		M = new ArrayList<>();
		for (int i=0; i<=n; i++)
			M.add(new HashMap<>());
		
		visited = new boolean[n+1];
		res = new int[n+1];
		sum = new long[n+1];
		
		S = new ArrayList<>();
		M = new ArrayList<>();
		
		for (int i=0; i<=n; i++)
		{
			S.add(new HashMap<>());
			M.add(new HashMap<>());
		}
		
		dfs(1);
		
		for (int i=1; i<=n; i++)
			io.print(sum[i]+" ");
		
	}
	
}

class Kattio extends PrintWriter {
	public Kattio(InputStream i) {
		super(new BufferedOutputStream(System.out));
		r = new BufferedReader(new InputStreamReader(i));
	}

	public Kattio(InputStream i, OutputStream o) {
		super(new BufferedOutputStream(o));
		r = new BufferedReader(new InputStreamReader(i));
	}

	public boolean hasMoreTokens() {
		return peekToken() != null;
	}

	public int getInt() {
		return Integer.parseInt(nextToken());
	}

	public double getDouble() {
		return Double.parseDouble(nextToken());
	}

	public long getLong() {
		return Long.parseLong(nextToken());
	}

	public String getWord() {
		return nextToken();
	}

	private BufferedReader r;
	private String line;
	private StringTokenizer st;
	private String token;

	private String peekToken() {
		if (token == null)
			try {
				while (st == null || !st.hasMoreTokens()) {
					line = r.readLine();
					if (line == null)
						return null;
					st = new StringTokenizer(line);
				}
				token = st.nextToken();
			} catch (IOException e) {
			}
		return token;
	}

	private String nextToken() {
		String ans = peekToken();
		token = null;
		return ans;
	}
}
