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.util.*;
import java.io.*;
public class E600 {
public static void main(String[] args) throws IOException
{
    FS input = new FS(System.in);
    int n = input.nextInt();
    int[] vs = new int[n];
    for(int i = 0; i<n; i++) vs[i] = input.nextInt();
    ArrayList<Integer>[] g = new ArrayList[n];
    for(int i = 0; i<n; i++) g[i] = new ArrayList<Integer>();
    for(int i = 0; i<n-1; i++)
    {
        int a = input.nextInt()-1, b = input.nextInt()-1;
        g[a].add(b);
        g[b].add(a);
    }
    int[] ps = new int[n];
    Arrays.fill(ps,  -1);
    ps[0] = -2;
    Queue<Integer> q = new LinkedList<Integer>();
    int[] order = new int[n];
    int pos = 0;
    q.add(0);
    while(!q.isEmpty())
    {
        int at = q.poll();
        order[pos++] = at;
        for(int e : g[at])
        {
            if(e == ps[at]) continue;
            ps[e] = at;
            q.add(e);
        }
    }
    long[] res = new long[n];
    Map[] maps = new Map[n];
    for(int i = 0; i<n; i++)
    {
        HashMap<Integer, Integer> cur = new HashMap<Integer, Integer>();
        cur.put(vs[i],  1);
        maps[i] = new Map(cur, 1, vs[i]);
    }
    for(int ii = n-1; ii>=0; ii--)
    {
        int i = order[ii];
        res[i] = maps[i].sum;
        if(i == 0) break;
        //System.out.println(maps[i].map);
        maps[ps[i]] = merge(maps[ps[i]], maps[i]);
    }
    PrintWriter out = new PrintWriter(System.out);
    for(int i = 0; i<n; i++)
        out.print(res[i] + " ");
    out.close();
}
static int mm, ss;
static Map merge(Map a, Map b)
{
    if(a.map.size() > b.map.size())
        return merge(b, a);
    long sum = b.sum;
    int max = b.max;
    for(int x : a.map.keySet())
    {
        int cur = a.map.get(x);
        b.map.put(x, b.map.containsKey(x) ? cur + b.map.get(x) : cur);
        int other = b.map.get(x);
        if(other > max)
        {
            max = other;
            sum = x;
        }
        else if(other == max)
        {
            sum += x;
        }
    }
    return new Map(b.map, max, sum);
}
static class Map
{
    HashMap<Integer, Integer> map;
    int max;
    long sum;
    Map(HashMap<Integer, Integer> map, int max, long sum)
    {
        this.map = map;
        this.max = max;
        this.sum = sum;
    }
}
static class FS
{
    BufferedReader br;
    StringTokenizer st;
    FS(InputStream in)
    {
        br = new BufferedReader(new InputStreamReader(in));
    }
    String next() throws IOException
    {
        while(st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }
    int nextInt() throws IOException
    {
        return Integer.parseInt(next());
    }
}
}
