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
/**
 * ******* Created on 12/11/19 6:31 AM*******
 */

import java.io.*;
import java.util.*;

public class E600 implements Runnable {

    private static final int MAX = (int) 1e5 + 10;
    private static final int MOD = (int) 1e9 + 7;
    List<Integer>[] edges = new List[MAX];
    private void solve() throws IOException {
        int t = 1;
        while (t-- > 0) {
            int n = reader.nextInt();
            for(int i=0;i<n;i++){
                edges[i]= new ArrayList<>();
                cl[i] =  new HashMap<>();
            }
            for(int i=0;i<n;i++) {
                int f = reader.nextInt();
                res[i] = f;
                cn[i]=1;
                cl[i].put(f,1L);
            }

            for(int i=0;i<n-1;i++){
                int x =reader.nextInt();
                int y = reader.nextInt();
                x--;y--;
                edges[x].add(y);
                edges[y].add(x);
            }
            dfs(0,-1);

            for(int i=0;i<n;i++)
                writer.print(res[i]+" ");
        }
    }
    long[] res =new long[MAX];
    Map<Integer,Long>[] cl = new Map[MAX];
    long[] cn =new long[MAX];
    private void dfs(int v, int p) {
        for(int i=0;i< edges[v].size();i++){
            int u = edges[v].get(i);
            if(u ==p)
                continue;
            dfs(u,v);
            if(cl[v].size() < cl[u].size()){
                Map<Integer, Long> temp= cl[v];
                cl[v] = cl[u];
                cl[u] =temp;
                cn[v] = cn[u];
                res[v] = res[u];
            }
            for(int key : cl[u].keySet()){
                int a = key;
                long b =cl[u].get(key);
                if(cl[v].containsKey(a))
                    cl[v].put(a, cl[v].get(a)+b);
                else
                    cl[v].put(a,b);
                if(cl[v].get(a) == cn[v]){
                    res[v] += a;
                }
                if(cl[v].get(a) >cn[v]){
                    res[v]=a;
                    cn[v]= cl[v].get(a);
                }
            }
        }
    }

    private  Map<Integer, Integer> swap(Map<Integer, Integer> c1, Map<Integer, Integer> c2) {
        return c2;
    }

    public static void main(String[] args) throws IOException {
        try (Input reader = new StandardInput(); PrintWriter writer = new PrintWriter(System.out)) {
            new E600().run();
        }
    }

    StandardInput reader;
    PrintWriter writer;

    @Override
    public void run() {
        try {
            reader = new StandardInput();
            writer = new PrintWriter(System.out);
            solve();
            reader.close();
            writer.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    interface Input extends Closeable {
        String next() throws IOException;

        default int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        default long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        default double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        default int[] readIntArray() throws IOException {
            return readIntArray(nextInt());
        }

        default int[] readIntArray(int size) throws IOException {
            int[] array = new int[size];
            for (int i = 0; i < array.length; i++) {
                array[i] = nextInt();
            }
            return array;
        }

        default long[] readLongArray(int size) throws IOException {
            long[] array = new long[size];
            for (int i = 0; i < array.length; i++) {
                array[i] = nextLong();
            }
            return array;
        }
    }

    private static class StandardInput implements Input {
        private final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        private StringTokenizer stringTokenizer;

        @Override
        public void close() throws IOException {
            reader.close();
        }

        @Override
        public String next() throws IOException {
            if (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
                stringTokenizer = new StringTokenizer(reader.readLine());
            }
            return stringTokenizer.nextToken();
        }
    }
}
