Byteasar is busy preparing a task for a programming contest. Has has already written a sketch of the content:
There are $n$ cities in Byteotia, connected by $n-1$ bidirectional roads in such a way that using the road network it is possible to drive between any two of the cities. It takes one hour to cover the distance between two directly connected cities. Cities are numbered from $1$ to $n$. The number of inhabitants living in the city $i$ is equal to $a_i$.
Next year elections are to be held in Byteotia. In order to have a full control over the conduct of the voting process, the King of Byteotia decided that the vote will be held in one city only. All Byteotian residents are to go to the city, where the ballot will be held, using the the shortest way, and they would vote there. Now all that remains is to choose the city where the voting will take place. This choice depends on many factors. In particular, for each city $i$, we would like to calculate the total time required by all Byteotian residents to reach the city $i$ (we indicate this value by $b_i$).
Byteasar had already prepared an extremely difficult set of tests to the task, but accidentally lost half of the data. Now, all that remained out of each test were only the descriptions of road connections and output files containing the $b_i$ values. On this basis, he would like to restore the data concerning the population of each Byteotian city.
Input Format
The first line of input contains an integer $n$ ($2 \leq n \leq 300\,000$) denoting the number of Byteotian cities. Each of the following $n-1$ lines contains a description of one road connection in the form of a pair of integers $x_i$, $y_i$ ($1 \leq x_i, y_i \leq n$). They indicate that the cities $x_i$ and $y_i$ have a road connection. The subsequent line contains a sequence of $n$ integers $b_i$ ($0 \leq b_i \leq 10^9$).
Output Format
Produce a single line containing a sequence of $n$ integers $a_i$. The number $a_i$ should indicate the population of Byteotian city number $i$. After solving Byteasar's exam task, for a given string $a_i$ we should receive string $b_i$ provided at the Input.
The input data are selected in such a way that a solution always exists and is unique.
Examples
Input
2 1 2 17 31
Output
31 17