Предыстория
«梦里鲜红的蔷薇» «睁眼是苍白的玫瑰»
На бесконечном бинарном дереве растет куст роз, на котором распустилось $n$ роз, образующих связную компоненту, содержащую корень. Заклинание представляет собой строку из $0$ и $1$ длиной $m$. Если произнести заклинание над розой, магический контур будет передаваться вниз в соответствии с символами заклинания: если символ равен $0$, контур передается к левому потомку, если $1$ — к правому. Если соответствующего потомка не существует, магия терпит неудачу. Для каждой розы определите, к какой розе приведет заклинание, если произнести его над ней, или выведите $0$, если магия терпит неудачу.
Входные данные
Первая строка содержит целое положительное число $n$ — количество роз. Далее следуют $n - 1$ строк, каждая из которых содержит три числа $u, v, f$, означающих, что роза $u$ соединена с розой $v$ через символ $f$. Следующая строка содержит целое положительное число $m$ — длину заклинания. Последняя строка содержит строку из $0$ и $1$ длиной $m$, представляющую заклинание.
Выходные данные
Выведите одну строку из $n$ целых чисел, где $i$-е число обозначает розу, к которой приведет заклинание, произнесенное над $i$-й розой. Если магия терпит неудачу, выведите $0$.
Подзадачи
| Подзадача | Баллы | Тесты | Ограничения | Специальные ограничения |
|---|---|---|---|---|
| 1 | 20 | 1, 2, 3, 4 | $n, m \le 10^3$ | Нет |
| 2 | 30 | 5, 6, 7 | $n, m \le 3 \times 10^5$ | A |
| 3 | 50 | 8, 9, 10 | $n, m \le 3 \times 10^5$ | Нет |
Специальное ограничение A: каждая роза имеет не более одного потомка.
Примеры
Входные данные 1
6 1 2 0 1 3 1 3 4 0 3 5 1 5 6 0 2 1 0
Выходные данные 1
4 0 6 0 0 0
Входные данные 2
См. файлы rose/rose2.in и rose/rose2.ans в директории участника.
Выходные данные 2
См. файлы rose/rose2.in и rose/rose2.ans в директории участника.