G. Tree problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In addition to binary trees on classes on discrete mathematics, Professor R. also talks about oriented trees. Let's define a directed tree. An oriented (directed) tree is an acyclic oriented graph in which only one vertex has a zero in-degree (no arcs lead into it), and all other vertices have a in-degree of 1 (there is exactly one arc leading into each of them). A vertex with a zero in-degree is called the root of the tree, vertices with a zero out-degree (from which no arc originates) are called terminal vertices or leaves. The figure below shows an example of an oriented tree.

After the class on oriented trees, the professor gave the students the following task as a home assignment.

Let's paint all the vertices of the oriented tree in some colors (denote by $$$c_i$$$ the color of the vertex with the number $$$i$$$). After that, for each vertex $$$i$$$ Professor wants to know what is the most frequent color in a subtree whose root is the vertex with the number $$$i$$$.

No matter how hard the students tried, they couldn't figure out how to solve this problem. Help them by writing a program that will answer all the queries made by Professor R.

Input

The first line contains the number $$$N$$$ $$$(1 \le N \le 2 \cdot 10^5)$$$ – the number of vertices in the tree.

The second line contains $$$N$$$ numbers $$$c_i$$$ separated by a space $$$(1 \le c_i \le 10^9)$$$ – the colors of the vertices, the $$$i$$$th number corresponds to the vertex with the number $$$i$$$.

The following $$$N - 1$$$ lines contain pairs of numbers $$$u$$$ and $$$v$$$ $$$(1 \le u, v \le N, u \ne v)$$$ describing the edges of the tree. The vertex $$$u$$$ corresponds to the beginning of the edge, $$$v$$$ corresponds to its end. It is guaranteed that the graph in the input data is an oriented tree. It is not guaranteed that vertex $$$1$$$ is the root of the tree.

Output

Output $$$N$$$ numbers, separated by a space, where the $$$i$$$th number is equal to the most frequent color in a subtree whose root is equal to $$$i$$$. If there are several required colors, you need to output the color with the lowest value.

Examples
Input
8
1 2 3 4 5 6 7 8
1 3
1 5
1 6
6 2
6 7
6 8
3 4
Output
1 2 3 4 5 2 7 8
Input
8
1 2 1 1 1 2 2 2
1 3
1 5
1 6
6 2
6 7
6 8
3 4
Output
1 2 1 1 1 2 2 2
Note

Trees in the input data correspond to the picture from the statement.