B. Roars III
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

In the middle of the Hundred Bytes Wood grows an unusual tree inhabited by roaring snails. This tree consists of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$ connected in a connected graph with $$$n-1$$$ edges. At the beginning, there is at most one male roaring snail in each vertex of the tree.

In a moment, a female will appear in a certain vertex of the tree and will start roaring. Each time the female roars, one male will move along an edge to an adjacent vertex of the tree closer to the female. However, the male cannot move if there is already another male in the target vertex, or if it is already in the same vertex as the female. The female stops roaring if after the next roar no male could make a move.

You are given a description of the tree inhabited by roaring snails as input. For each vertex, you also receive information about whether a male snail is present in it. For each vertex, determine the maximum number of times the female could roar if she were to be in that vertex. We assume that the males move in a way that maximizes the number of roars.

Input

The first line of the input contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) representing the number of vertices in the tree under consideration.

The second line of the input contains a word consisting of $$$n$$$ characters 0 and 1. If the $$$i$$$-th character of this word is $$$\texttt{1}$$$, then there is a male snail in the $$$i$$$-th vertex of the tree. If the $$$i$$$-th character of this word is $$$\texttt{0}$$$, then there is no male snail in the $$$i$$$-th vertex of the tree.

The next $$$n-1$$$ lines contain two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i,b_i \leq n; a_i \neq b_i$$$) indicating that the vertices $$$a_i$$$ and $$$b_i$$$ of the tree are connected by an edge.

Output

The output should contain $$$n$$$ integers in a single line; the $$$i$$$-th integer should indicate the maximum number of roars the female can make if she were to be in the $$$i$$$-th vertex of the tree.

Example
Input
5
10101
1 2
2 3
2 4
4 5
Output
2 2 2 3 3
Note

The tree in the sample test is shown below. The males are located in the vertices shaded in gray.

If the female is in the first vertex, she can roar at most twice, for example by first attracting the male from the third vertex to the second, and then the male from the fifth vertex to the fourth:

If the female is in the fourth vertex, as long as the male from the fifth vertex does not move, she can roar up to three times: