Alice and Bob are going to celebrate Christmas by playing a game with a tree of presents. The tree has $n$ nodes (numbered $1$ to $n$, with some node $r$ as its root). There are $a_i$ presents are hanging from the $i$-th node.

Before beginning the game, a special integer $k$ is chosen. The game proceeds as follows:

• Alice begins the game, with moves alternating each turn;
• in any move, the current player may choose some node (for example, $i$) which has depth at least $k$. Then, the player picks some positive number of presents hanging from that node, let's call it $m$ $(1 \le m \le a_i)$;
• the player then places these $m$ presents on the $k$-th ancestor (let's call it $j$) of the $i$-th node (the $k$-th ancestor of vertex $i$ is a vertex $j$ such that $i$ is a descendant of $j$, and the difference between the depth of $j$ and the depth of $i$ is exactly $k$). Now, the number of presents of the $i$-th node $(a_i)$ is decreased by $m$, and, correspondingly, $a_j$ is increased by $m$;
• Alice and Bob both play optimally. The player unable to make a move loses the game.

For each possible root of the tree, find who among Alice or Bob wins the game.

Note: The depth of a node $i$ in a tree with root $r$ is defined as the number of edges on the simple path from node $r$ to node $i$. The depth of root $r$ itself is zero.

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.

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.