Description

Input

The first line contains two space-separated integers $n$ and $k$ $(3 \le n \le 10^5, 1 \le k \le 20)$.

The next $n-1$ lines each contain two integers $x$ and $y$ $(1 \le x, y \le n, x \neq y)$, denoting an undirected edge between the two nodes $x$ and $y$. These edges form a tree of $n$ nodes.

The next line contains $n$ space-separated integers denoting the array $a$ $(0 \le a_i \le 10^9)$.

Output

Output $n$ integers, where the $i$-th integer is $1$ if Alice wins the game when the tree is rooted at node $i$, or $0$ otherwise.

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

1 0 0 1 1

Note

Let us calculate the answer for sample input with root node as 1 and as 2.

Root node 1

Alice always wins in this case. One possible gameplay between Alice and Bob is:

• Alice moves one present from node 4 to node 3.
• Bob moves four presents from node 5 to node 2.
• Alice moves four presents from node 2 to node 1.
• Bob moves three presents from node 2 to node 1.
• Alice moves three presents from node 3 to node 1.
• Bob moves three presents from node 4 to node 3.
• Alice moves three presents from node 3 to node 1.

Bob is now unable to make a move and hence loses.

Root node 2

Bob always wins in this case. One such gameplay is:

• Alice moves four presents from node 4 to node 3.
• Bob moves four presents from node 5 to node 2.
• Alice moves six presents from node 3 to node 1.
• Bob moves six presents from node 1 to node 2.

Alice is now unable to make a move and hence loses.