Given an undirected tree with $n$ vertices. Initially, each vertex $i$ ($1 \le i \le n$) has a weight $c_i$. Consider the following operation: * Let $\text{deg}_x$ be the degree of vertex $x$. If there exists a vertex $x$ such that $c_x \ge \text{deg}_x$, choose any vertex $x$ satisfying this condition, subtract $\text{deg}_x$ from $c_x$, and add 1 to the weight of all neighbors of $x$.

A sequence of weights $(c_1, \dots, c_n)$ is called a terminal state if and only if the above operation cannot be performed, i.e., all vertices $y$ satisfy $c_y < \text{deg}_y$.

It can be proven that for any undirected tree and any sequence of weights, only the following two cases are possible: 1. Regardless of how the operations are performed, a terminal state is reached after a finite number of operations, and any sequence of operations leads to the same terminal state. 2. Regardless of how the operations are performed, it is impossible to reach a terminal state after a finite number of operations.

You need to determine which of the above cases the given initial state belongs to. If it belongs to the first case, you need to output the unique terminal state that can be reached by performing the operations.

Input

The first line contains a positive integer $n$ ($1 \le n \le 10^6$), representing the number of vertices in the tree. The next $n-1$ lines each contain two integers $x, y$ ($1 \le x, y \le n$), representing an edge of the tree. The next line contains $n$ integers $c_i$ ($0 \le c_i \le 10^9$), representing the initial weights of the vertices.

Output

If it is impossible to reach a terminal state within a finite number of operations, output -1. Otherwise, output a single line containing $n$ integers, describing the weights of each vertex in the terminal state in order.

Examples

Input 1

6
1 2
2 3
2 4
1 5
4 6
1 1 0 0 1 1

Output 1

1 2 0 1 0 0

Note 1

Consider the following sequence of operations: Perform the operation on 6, resulting in the weight sequence $(1, 1, 0, 1, 1, 0)$; Perform the operation on 5, resulting in the weight sequence $(2, 1, 0, 1, 0, 0)$; Perform the operation on 1, resulting in the weight sequence $(0, 2, 0, 1, 1, 0)$; Perform the operation on 5, resulting in the weight sequence $(1, 2, 0, 1, 0, 0)$.

The weight sequence $(1, 2, 0, 1, 0, 0)$ is a terminal state, so output 1 2 0 1 0 0.

Input 2

12
1 2
1 3
2 4
3 5
5 6
2 7
7 8
4 9
8 10
5 11
3 12
2 0 0 0 1 0 1 0 1 1 0 1

Output 2

0 1 2 1 1 0 1 1 0 0 0 0

Input 3

See 3.in and 3.ans in the problem directory.