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.*;

/**
 * Created by noureldin on 2/20/17.
 */
public class main {
    private static Character [] type;
    private static LinkedList<Integer> [] G;
    private static int [] color,cnt,siz,pref_child,dfs_in,dfs_out,ord;
    private static long [] sum,ans;
    private static int dfs_time = 0,mx;

    private static int dfs(int u,int p){
        siz[u] = 1;
        pref_child[u] = -1;
        ord[dfs_time] = u;
        dfs_in[u] = dfs_time++;
        for (int v: G[u]) if(v != p) {
            siz[u] += dfs(v,u);
            if(pref_child[u] == -1 || siz[v] > siz[pref_child[u]])
                pref_child[u] = v;
        }
        dfs_out[u] = dfs_time - 1;
        return siz[u];
    }
    private static void add(int c){
        if(cnt[c] != 0) sum[cnt[c]] -= c;
        ++cnt[c];
        sum[cnt[c]] += c;
        if(cnt[c] > mx) mx = cnt[c];
    }
    private static void erase(int c){
        sum[cnt[c]] -= c;
        if(mx == cnt[c] && sum[cnt[c]] == 0) mx--;
        --cnt[c];
        if(cnt[c] != 0) sum[cnt[c]] += c;
    }
    private static void dfs(int u,int p,boolean keep){
        for (int v: G[u]) if(v != p && v != pref_child[u]) dfs(v,u,false);
        if(pref_child[u] != -1) dfs(pref_child[u], u, true);

        add(color[u]);

        for(int v : G[u]) if(v != p && v != pref_child[u]){
            for(int i = dfs_in[v];i <= dfs_out[v];i++){
                int t = ord[i];
                add(color[t]);
            }
        }

        ans[u] = sum[mx];
        if(!keep){
            for(int i = dfs_in[u];i <= dfs_out[u];i++) {
                int t = ord[i];
                erase(color[t]);
            }
        }
    }
    public static void main(String[] args) throws Exception {
        IO io = new IO(null,null);
        int n = io.getNextInt();
        G = new LinkedList[n + 1];
        color = new int[n + 1];
        cnt = new int[n + 1];
        sum = new long[n + 1];
        siz = new int[n + 1];
        pref_child = new int[n + 1];
        dfs_in = new int[n + 1];
        dfs_out = new int[n + 1];
        ord = new int[n];
        ans = new long [n + 1];
        for(int i = 1;i <= n;i++) {
            G[i] = new LinkedList<Integer>();
            color[i] = io.getNextInt();
        }
        for(int i = 0;i < n-1;i++){
            int x = io.getNextInt(),y = io.getNextInt();
            G[x].add(y);
            G[y].add(x);
        }
        dfs(1,0);
        dfs(1,0,true);
        for(int i = 1;i <= n;i++) io.write(Long.toString(ans[i]) + ((i == n) ? "\n" : " "));
        io.close();
    }

}

class IO{
    private BufferedReader br;
    private StringTokenizer st;
    private PrintWriter writer;
    private String inputFile,outputFile;

    public String getNext() throws FileNotFoundException, IOException{
        while(st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    public int getNextInt() throws FileNotFoundException, IOException{
        return Integer.parseInt(getNext());
    }

    public void write(String s) throws IOException{
        writer.print(s);
    }

    public void println(String s) throws  IOException{
        writer.println(s);
    }
    public IO(String x,String y) throws FileNotFoundException, IOException{
        inputFile = x;
        outputFile = y;
        if(x != null) br = new BufferedReader(new FileReader(inputFile));
        else br = new BufferedReader(new InputStreamReader(System.in));
        if(y != null) writer = new PrintWriter(new BufferedWriter(new FileWriter(outputFile)));
        else writer = new PrintWriter(new OutputStreamWriter(System.out));
    }

    protected void close() throws IOException{
        br.close();
        writer.close();
    }
}

