F. Рождественская игра
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб собираются отмечать Рождество, играя в игру с деревом подарков. Дерево состоит из $$$n$$$ вершин (пронумерованных от $$$1$$$ до $$$n$$$, вершина $$$r$$$ является корнем). На $$$i$$$-й вершине висят $$$a_i$$$ подарков.

Перед началом игры выбирается некоторое целое число $$$k$$$. Затем игра проходит следующим образом:

  • Алиса начинает игру, затем ходы совершаются обоими игроками по очереди;
  • на каждом ходу текущий игрок выбирает некоторую вершину (например, $$$i$$$), которая находится на глубине хотя бы $$$k$$$. Затем игрок снимает некоторое положительное целое число подарков, которые висят на этой вершине, — назовем его $$$m$$$ $$$(1 \le m \le a_i)$$$;
  • затем игрок вешает эти $$$m$$$ подарков на $$$k$$$-го предка (назовем его $$$j$$$) $$$i$$$-й вершины ($$$k$$$-м предком вершины $$$i$$$ назовем такую вершину $$$j$$$, что $$$i$$$ — потомок $$$j$$$, а глубина $$$j$$$ ровно на $$$k$$$ меньше глубины $$$i$$$). Теперь количество подарков на $$$i$$$-й вершине $$$(a_i)$$$ уменьшилось на $$$m$$$, а $$$a_j$$$, соответственно, увеличилось на $$$m$$$;
  • Алиса и Боб играют оптимально. Тот, кто не может совершить ход, проигрывает.

Для каждого возможного корня дерева сообщите, кто выиграет игру — Алиса или Боб.

Глубина вершины $$$i$$$ в дереве с корнем $$$r$$$ определяется, как количество ребер на простом пути из вершины $$$r$$$ до вершины $$$i$$$. Глубина корня $$$r$$$ равна нулю.

Входные данные

В первой строке записаны два целых числа $$$n$$$ и $$$k$$$ $$$(3 \le n \le 10^5, 1 \le k \le 20)$$$.

В каждой из следующих $$$n-1$$$ строк записаны два целых числа $$$x$$$ и $$$y$$$ $$$(1 \le x, y \le n, x \neq y)$$$, описывающие неориентированное ребро между двумя вершинами $$$x$$$ и $$$y$$$. Эти ребра образуют дерево из $$$n$$$ вершин.

В следующей строке записаны $$$n$$$ целых чисел, задающих массив $$$a$$$ $$$(0 \le a_i \le 10^9)$$$.

Выходные данные

Выведите $$$n$$$ целых чисел, где $$$i$$$-е число равно $$$1$$$, если Алиса выиграет игру, если дерево подвешено за вершину $$$i$$$, и $$$0$$$ в противном случае.

Пример
Входные данные
5 1
1 2
1 3
5 2
4 3
0 3 2 4 4
Выходные данные
1 0 0 1 1 
Примечание

Посчитаем ответ для примера с корнем в 1 и в 2.

Корень 1

Алиса всегда выигрывает в данном случае. Возможная игра между Алисой и Бобом выглядит так:

  • Алиса перемещает один подарок из вершины 4 в вершину 3.
  • Боб перемещает четыре подарка из вершины 5 в вершину 2.
  • Алиса перемещает четыре подарка из вершины 2 в вершину 1.
  • Боб перемещает три подарка из вершины 2 в вершину 1.
  • Алиса перемещает три подарка из вершины 3 в вершину 1.
  • Боб перемещает три подарка из вершины 4 в вершину 3.
  • Алиса перемещает три подарка из вершины 3 в вершину 1.

Боб не может сделать ход, а потому проигрывает.

Корень 2

Боб всегда выигрывает в данном случае. Пример игры:

  • Алиса перемещает четыре подарка из вершины 4 в вершину 3.
  • Боб перемещает четыре подарка из вершины 5 в вершину 2.
  • Алиса перемещает шесть подарков из вершины 3 в вершину 1.
  • Боб перемещает шесть подарков из вершины 1 в вершину 2.

Алиса не может сделать ход, а потому проигрывает.