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: 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. The first line contains two space-separated integers n and k (3 <= n <= 10^5, 1 <= k <= 20) . The next n-1 lines each contain two integers x and y (1 <= x, y <= 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 <= a_i <= 10^9) . 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. 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: 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 is now unable to make a move and hence loses.