Na nieskończenie rozciągającym się drzewie binarnym rośnie krzew róż, na którym zakwitło łącznie $n$ róż, tworzących spójny podzbiór zawierający korzeń. Zaklęcie jest ciągiem znaków $0$ i $1$ o długości $m$. Jeśli wypowie się zaklęcie nad daną różą, magiczny obwód będzie przekazywany w dół zgodnie z kolejnymi znakami zaklęcia: jeśli znakiem jest $0$, obwód przechodzi do lewego dziecka, a jeśli $1$ — do prawego dziecka. Jeśli odpowiednie dziecko nie istnieje, magia zawodzi. Dla każdej róży należy sprawdzić, czy wypowiedzenie nad nią zaklęcia spowoduje niepowodzenie magii, a jeśli się powiedzie, do której róży dotrze obwód.
Wejście
W pierwszej linii wejścia znajduje się liczba całkowita $n$, oznaczająca liczbę róż. Następnie w $n-1$ liniach podano po 3 liczby $u, v, f$, oznaczające, że z róży $u$ można przejść do róży $v$ za pomocą znaku $f$. W kolejnej linii znajduje się liczba całkowita $m$, oznaczająca długość zaklęcia. W ostatniej linii znajduje się ciąg znaków $0$ i $1$ o długości $m$, reprezentujący zaklęcie.
Wyjście
Wypisz w jednej linii $n$ liczb całkowitych, gdzie $i$-ta liczba oznacza różę, do której dotrze obwód po wypowiedzeniu zaklęcia nad $i$-tą różą. Jeśli magia zawiedzie, wypisz $0$.
Przykład 1
Wejście 1
6 1 2 0 1 3 1 3 4 0 3 5 1 5 6 0 2 1 0
Wyjście 1
4 0 6 0 0 0
Przykład 2
Dane znajdują się w plikach rose/rose2.in oraz rose/rose2.ans w katalogu zawodnika.
Podzadania
Dla 100% danych wejściowych zachodzą warunki: $1 \le n, m \le 3 \times 10^5$, $1 \le u, v \le n$, $0 \le f \le 1$.
| Testy | $n, m$ | Ograniczenia dodatkowe |
|---|---|---|
| 1, 2, 3, 4 | $\le 10^3$ | |
| 5, 6, 7 | $\le 3 \times 10^5$ | A |
| 8, 9, 10 | $\le 3 \times 10^5$ |
Ograniczenie dodatkowe A: Każda róża posiada co najwyżej jedną gałąź prowadzącą w dół.