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.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

import javafx.util.Pair;

public class Main {

    static Graph tree;
    static int[] colors;
    static long[] dominatingColors;
    static int[] counts;
    static Map<Integer, Integer>[] frequencies;

    public static void solve() {
        int n = IO.readInt();
        colors = IO.readIntArray(n);
        dominatingColors = new long[n];
        counts = new int[n];

        tree = new Graph(n);
        for (int index = 0; index < n - 1; ++index) {
            tree.addEdge(IO.readInt() - 1, IO.readInt() - 1);
        }

        frequencies = (Map<Integer, Integer>[]) new Map[n];

        dfs(0, -1);

        StringBuilder sb = new StringBuilder();
        for (long c : dominatingColors) {
            sb.append(c).append(" ");
        }
        IO.println(sb);
    }

    private static void dfs(int v, int from) {
        int biggest = -1;
        for (int c : tree.adj(v)) {
            if (c == from) {
                continue;
            }
            dfs(c, v);
            if (biggest == -1 || frequencies[c].size() > frequencies[biggest].size()) {
                biggest = c;
            }
        }

        if (biggest >= 0) {
            frequencies[v] = frequencies[biggest];
            dominatingColors[v] = dominatingColors[biggest];
            counts[v] = counts[biggest];

            for (int c : tree.adj(v)) {
                if (c != biggest && c != from) {
                    for (Map.Entry<Integer, Integer> e : frequencies[c].entrySet()) {
                        add(v, e.getKey(), e.getValue());
                    }
                }
            }
        }
        else {
            frequencies[v] = new TreeMap<>();
        }
        add(v, colors[v], 1);
    }

    private static void add(int v, int color, int count) {
        Integer oldCount = frequencies[v].get(color);
        int newCount = oldCount == null ? count : oldCount + count;
        frequencies[v].put(color, newCount);
        if (newCount > counts[v]) {
            counts[v] = newCount;
            dominatingColors[v] = color;
        }
        else if (newCount == counts[v]) {
            dominatingColors[v] += color;
        }
    }

    public static class Graph {
        private final int V;
        private final List<Integer>[] adj;
        private int E;

        public Graph(int V) {
            this.V = V;
            adj = (List<Integer>[]) new List[V];
            for (int v = 0; v < V; ++v) {
                adj[v] = new LinkedList<>();
            }
        }

        public int V() {
            return V;
        }

        public int E() {
            return E;
        }

        public Iterable<Integer> adj(int v) {
            return adj[v];
        }

        public void addEdge(int v, int w) {
            adj[v].add(w);
            adj[w].add(v);
            E++;
        }
    }

    static Map<Integer, Integer> join(Map<Integer, Integer> map1, Map<Integer, Integer> map2) {
        if (map2.size() > map1.size()) {
            Map<Integer, Integer> temp = map1;
            map1 = map2;
            map2 = temp;
        }
        for (Map.Entry<Integer, Integer> e : map2.entrySet()) {
            Integer value = map1.get(e.getKey());
            if (value == null) {
                value = e.getValue();
            }
            else {
                value += e.getValue();
            }
            map1.put(e.getKey(), value);
        }
        return map1;
    }

    // Input/Output ================================
    public static class IO {

        private static Scanner scanner;
        private static PrintWriter writer;

        public static void setUp(InputStream in, OutputStream out) {
            scanner = new Scanner(new java.io.BufferedInputStream(in));
            writer = new PrintWriter(out);
        }

        public static boolean isEmpty() {
            return !scanner.hasNext();
        }

        public static boolean hasNextLine() {
            return scanner.hasNextLine();
        }

        public static String readLine() {
            String line;
            try {
                line = scanner.nextLine();
            }
            catch (Exception e) {
                line = null;
            }
            return line;
        }

        public static String readString() {
            return scanner.next();
        }

        public static int readInt() {
            return scanner.nextInt();
        }

        public static int[] readIntArray(int n) {
            int[] a = new int[n];
            for (int index = 0; index < n; ++index) {
                a[index] = readInt();
            }
            return a;
        }

        public static Pair<Integer, Integer>[] readIntArrayWithIndexes(int n) {
            Pair<Integer, Integer>[] a = new Pair[n];
            for (int index = 0; index < n; ++index) {
                a[index] = new Pair<>(index, readInt());
            }
            return a;
        }

        public static double readDouble() {
            return scanner.nextDouble();
        }

        public static float readFloat() {
            return scanner.nextFloat();
        }

        public static long readLong() {
            return scanner.nextLong();
        }

        public static char readChar() {
            return scanner.findInLine("[^\\s]").charAt(0);
        }

        public static void print(Object o) {
            writer.print(o);
            writer.flush();
        }

        public static void println(Object o) {
            writer.println(o);
            writer.flush();
        }
    }

    // Algorithms ================================

    private static class Algo {

        private static int binSearch(int[] array, int n, int lo, int hi) {
            if (lo > hi) {
                return lo;
            }

            int mid = lo + (hi - lo) / 2;
            int cmp = (int) java.lang.Math.signum(n - array[mid]);
            if (cmp < 0) {
                return binSearch(array, n, lo, mid - 1);
            }
            else if (cmp == 0) {
                return mid;
            }
            else {
                return binSearch(array, n, mid + 1, hi);
            }
        }

        private static void permutations(int n) {
            int[] p = new int[n];
            for (int index = 0; index < n; ++index) {
                p[index] = index + 1;
            }

            while (true) {
                IO.println(Arrays.toString(p));

                int k = n - 1;
                while (k > 0) {
                    if (p[k] < p[k - 1]) {
                        k--;
                    }
                    else {
                        break;
                    }
                }
                if (k == 0) {
                    break;
                }
                int j = n - 1;
                while (p[j] < p[k - 1]) {
                    j--;
                }

                int t = p[j];
                p[j] = p[k - 1];
                p[k - 1] = t;

                int i = 0;
                while (k + i < n - 1 - i) {
                    t = p[k + i];
                    p[k + i] = p[n - i - 1];
                    p[n - i - 1] = t;
                    i++;
                }
            }
        }

        private static boolean isPrime(int number) {
            if (number <= 1) {
                return false;
            }
            if (number <= 3) {
                return true;
            }
            if (number % 2 == 0 || number % 3 == 0) {
                return false;
            }
            int i = 5;
            while (i * i <= number) {
                if (number % i == 0 || number % (i + 2) == 0) {
                    return false;
                }
                i += 6;
            }
            return true;
        }

        private static boolean isPrimeOrOne(int number) {
            return number == 1 || isPrime(number);
        }

        private static boolean isPalindrome(int number) {
            int n = number;
            int reverse = 0;
            while (n > 0) {
                reverse *= 10;
                reverse += (n % 10);
                n /= 10;
            }
            return reverse == number;
        }

        public static int gcd(int a, int b) {
            while (b != 0) {
                int tmp = a % b;
                a = b;
                b = tmp;
            }
            return a;
        }
    }

    private static class Math2 {

        static long c(int n, int k) {
            if (n == 0 && k == 0) {
                return 1;
            }
            int d = 1000;
            int l = 1000000007;
            long[][] c = new long[d + 1][d + 1];
            for (int i = 1; i <= d; ++i) {
                for (int j = 0; j <= i; ++j) {
                    if (i == j || j == 0) {
                        c[i][j] = 1;
                    }
                    else {
                        c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % l;
                    }
                }
            }
            return c[n][k];
        }
    }

    static class Pair<K, V> {
        K key;
        V value;

        Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    public static void main(String[] args) {
        IO.setUp(System.in, System.out);
        /*
        try {
            IO.setUp(new FileInputStream("encode.in"), new FileOutputStream("encode.out"));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
            return;
        }
        */
        solve();
    }
}
