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.math.*;
import java.util.*;

public class CODEFORCES
{
	private InputStream is;
	private PrintWriter out;

	int c[], size[], st[], et[], rev[];
	long ans[];
	ArrayList<Integer> a[];
	int len = 0;

	void dfs1(int u, int p)
	{
		st[u] = ++len;
		rev[len] = u;
		for (int i : a[u])
		{
			if (i == p)
				continue;
			dfs1(i, u);
			size[u] += size[i];
		}
		size[u]++;
		et[u] = len;
	}

	int tmp[], mx = 0;
	long val = 0;

	void dfs2(int u, int p, int k)
	{
		int b = 0;
		int m = 0;
		for (int i : a[u])
		{
			if (i == p)
				continue;
			if (m < size[i])
			{
				m = size[i];
				b = i;
			}
		}
		for (int i : a[u])
		{
			if (i == p || i == b)
				continue;
			dfs2(i, u, 0);
		}
		if (b != 0)
			dfs2(b, u, 1);
		tmp[c[u]]++;
		if (tmp[c[u]] > mx)
		{
			mx = tmp[c[u]];
			val = c[u];
		} else if (tmp[c[u]] == mx)
			val += c[u];
		for (int i : a[u])
		{
			if (i == p || i == b)
				continue;
			for (int j = st[i]; j <= et[i]; j++)
			{
				tmp[c[rev[j]]]++;
				if (tmp[c[rev[j]]] > mx)
				{
					mx = tmp[c[rev[j]]];
					val = c[rev[j]];
				} else if (tmp[c[rev[j]]] == mx)
					val += c[rev[j]];
			}
		}
		ans[u] = val;
		if (k == 0)
		{
			for (int j = st[u]; j <= et[u]; j++)
				tmp[c[rev[j]]]--;
			val = 0;
			mx = 0;
		}
	}

	@SuppressWarnings("unchecked")
	void solve()
	{
		int n = ni();
		c = new int[n + 1];
		tmp = new int[n + 1];
		rev = new int[n + 1];
		size = new int[n + 1];
		for (int i = 1; i <= n; i++)
			c[i] = ni();
		a = new ArrayList[n + 1];
		for (int i = 1; i <= n; i++)
			a[i] = new ArrayList<Integer>();
		for (int i = 1; i < n; i++)
		{
			int x = ni();
			int y = ni();
			a[x].add(y);
			a[y].add(x);
		}
		ans = new long[n + 1];
		st = new int[n + 1];
		et = new int[n + 1];
		dfs1(1, 1);
		dfs2(1, 1, 1);
		for (int i = 1; i <= n; i++)
			out.print(ans[i] + " ");
		out.println();
	}

	void soln()
	{
		is = System.in;
		out = new PrintWriter(System.out);
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		tr(System.currentTimeMillis() - s + "ms");
	}

	public static void main(String[] args)
	{
		new CODEFORCES().soln();
	}

	// To Get Input
	// Some Buffer Methods
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;

	private int readByte()
	{
		if (lenbuf == -1)
			throw new InputMismatchException();
		if (ptrbuf >= lenbuf)
		{
			ptrbuf = 0;
			try
			{
				lenbuf = is.read(inbuf);
			} catch (IOException e)
			{
				throw new InputMismatchException();
			}
			if (lenbuf <= 0)
				return -1;
		}
		return inbuf[ptrbuf++];
	}

	private boolean isSpaceChar(int c)
	{
		return !(c >= 33 && c <= 126);
	}

	private int skip()
	{
		int b;
		while ((b = readByte()) != -1 && isSpaceChar(b))
			;
		return b;
	}

	private double nd()
	{
		return Double.parseDouble(ns());
	}

	private char nc()
	{
		return (char) skip();
	}

	private String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while (!(isSpaceChar(b)))
		{ // when nextLine, (isSpaceChar(b) && b != '
			// ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	private char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while (p < n && !(isSpaceChar(b)))
		{
			buf[p++] = (char) b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}

	private char[][] nm(int n, int m)
	{
		char[][] map = new char[n][];
		for (int i = 0; i < n; i++)
			map[i] = ns(m);
		return map;
	}

	private int[] na(int n)
	{
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}

	private int ni()
	{
		int num = 0, b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-')
		{
			minus = true;
			b = readByte();
		}

		while (true)
		{
			if (b >= '0' && b <= '9')
			{
				num = num * 10 + (b - '0');
			} else
			{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	private long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-')
		{
			minus = true;
			b = readByte();
		}

		while (true)
		{
			if (b >= '0' && b <= '9')
			{
				num = num * 10 + (b - '0');
			} else
			{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	private boolean oj = System.getProperty("ONLINE_JUDGE") != null;

	private void tr(Object... o)
	{
		if (!oj)
			System.out.println(Arrays.deepToString(o));
	}
}