***E. Lomsat gelral

E. Lomsat gelral

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

-------------------------------------------------EDITORIAL------------------------------------------------------
THIS PROBLEM CAN BE SOLVED IN MAY WAYS
1-> MO
2-> NORMAL DFS AND EACH NODE WILL CONTAIN A MAP

2 ND  METHOD IS VERY INTERESTING AND OFTEN I CONFUSED HOW ITS WORKING IN THE  TIME LIMIT AND ,  HOW MUCH MEMORIES IT NEEDED ..

SO FIRST  OF  DISCUSS THE SECOND APPROACH

The name of this problem is anagram for ''Small to large''. There is a reason for that :-) The author solution for this problem uses the classic technique for computing sets in tree. The simple solution is the following: let's find for each vertex v the ''map<int, int>'' — the number of occurences for each colour, ''set<pair<int, int>>'' — pairs the number of occurences and the colour, and the number sum — the sum of most frequent colours in subtree of v. To find that firstly we should find the same thing for all childs of v and then merge them to one. These solution is correct but too slow (it works in O(n2logn) time). Let's improve that solution: every time when we want to merge two map-s a and b let's merge the smaller one to larger simply by iterating over all elements of the smaller one (this is the ``Small to large''). Let's consider some vertex v: every time when vertex v will be moved from one map to another the size of the new map will be at least two times larger. So each vertex can be moved not over than logn times. Each moving can be done in O(logn)time. If we accumulate that values by all vertices then we get the complexity O(nlog2n).

I saw the solutions that differs from author's but this technique can be used in a lot of other problems.