Алиса и Боб собираются отмечать Рождество, играя в игру с деревом подарков. Дерево состоит из $$$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$$$ равна нулю.