Алиса и Боб собираются отмечать Рождество, играя в игру с деревом подарков. Дерево состоит из \(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\) целых чисел, где \(i\)-е число равно \(1\), если Алиса выиграет игру, если дерево подвешено за вершину \(i\), и \(0\) в противном случае.
Примечание
Посчитаем ответ для примера с корнем в 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.
Алиса не может сделать ход, а потому проигрывает.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 1
1 2
1 3
5 2
4 3
0 3 2 4 4
|
1 0 0 1 1
|