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
// practice with rainboy
import java.io.*;
import java.util.*;

public class CF600E extends PrintWriter {
	CF600E() { super(System.out, true); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF600E o = new CF600E(); o.main(); o.flush();
	}

	static Random rand = new Random();
	static class V {
		V l, r;
		int key, val, x;
		V(int key, int val) {
			this.key = key; this.val = val;
			x = rand.nextInt();
		}
	}
	V v_, l_, r_;
	void split(V v, int key) {
		if (v == null) {
			v_ = l_ = r_ = null;
		} else if (v.key < key) {
			split(v.r, key);
			v.r = l_; l_ = v;
		} else if (v.key > key) {
			split(v.l, key);
			v.l = r_; r_ = v;
		} else {
			v_ = v; l_ = v.l; r_ = v.r;
			v.l = v.r = null;
		}
	}
	V merge(V u, V v) {
		if (u == null)
			return v;
		if (v == null)
			return u;
		if (u.x < v.x) {
			u.r = merge(u.r, v);
			return u;
		} else {
			v.l = merge(u, v.l);
			return v;
		}
	}
	int add(int key, int val) {
		split(v_, key);
		if (v_ == null)
			v_ = new V(key, val);
		else
			v_.val += val;
		val = v_.val;
		v_ = merge(l_, merge(v_, r_));
		return val;
	}
	int get(int key) {
		split(v_, key);
		int val = v_ == null ? -1 : v_.val;
		v_ = merge(l_, merge(v_, r_));
		return val;
	}
	int[] next, jj; int __ = 1;
	int link(int l, int j) {
		next[__] = l; jj[__] = j;
		return __++;
	}
	int[] ao, cc, nn, kk; long[] ss; V[] vv;
	void init(int n, int m) {
		next = new int[1 + m * 2]; jj = new int[1 + m * 2];
		ao = new int[n]; cc = new int[n]; nn = new int[n]; kk = new int[n];
		ss = new long[n]; vv = new V[n];
	}
	void dfs(int p, int i) {
		int n = 1, j_ = -1;
		for (int l = ao[i]; l != 0; l = next[l]) {
			int j = jj[l];
			if (j != p) {
				dfs(i, j);
				n += nn[j];
				if (j_ == -1 || nn[j_] < nn[j])
					j_ = j;
			}
		}
		nn[i] = n;
		v_ = null;
		int k_ = 0; long s_ = 0;
		if (j_ != -1) {
			v_ = vv[j_]; k_ = kk[j_]; s_ = ss[j_];
		}
		int c, k = add(c = cc[i], 1);
		if (k_ < k) {
			k_ = k; s_ = c;
		} else if (k_ == k)
			s_ += c;
		for (int l = ao[i]; l != 0; l = next[l]) {
			int j = jj[l];
			if (j != p && j != j_)
				for (V v = vv[j]; v != null; v = merge(v.l, v.r)) {
					k = add(c = v.key, v.val);
					if (k_ < k) {
						k_ = k; s_ = c;
					} else if (k_ == k)
						s_ += c;
				}
		}
		vv[i] = v_; kk[i] = k_; ss[i] = s_;
	}
	void main() {
		int n = sc.nextInt();
		init(n, n - 1);
		cc = new int[n];
		for (int i = 0; i < n; i++)
			cc[i] = sc.nextInt();
		for (int h = 0; h < n - 1; h++) {
			int i = sc.nextInt() - 1;
			int j = sc.nextInt() - 1;
			ao[i] = link(ao[i], j);
			ao[j] = link(ao[j], i);
		}
		dfs(-1, 0);
		for (int i = 0; i < n; i++)
			print(ss[i] + " ");
		println();
	}
}
