"Red Roses and White Roses" (rose)

Background

"Red roses in dreams" "Pale roses when eyes open"

On an infinitely extending binary tree, there is a rose plant with $n$ roses, forming a connected component that includes the root node. A spell is a $01$ string of length $m$. If a spell is cast on a rose, a magic circuit will propagate downwards along the spell. The magic circuit follows each character of the spell one by one: if the character is $0$, it propagates to the left child; if it is $1$, it propagates to the right child. If the corresponding child does not exist, the magic fails. For each rose, if the spell is cast on it, will the magic fail? If it succeeds, which rose does it reach?

Input

The first line contains a positive integer $n$, representing the number of roses. The next $n - 1$ lines each contain three numbers $u, v, f$, indicating that $u$ extends to $v$ via character $f$. The next line contains a positive integer $m$, representing the length of the spell. The next line contains a $01$ string of length $m$, representing the spell.

Output

Output a single line containing $n$ integers. The $i$-th integer represents the rose reached when the spell is cast on the $i$-th rose. If the magic fails, output $0$.

Examples

Input 1

6
1 2 0
1 3 1
3 4 0
3 5 1
5 6 0
2
1 0

Output 1

4 0 6 0 0 0

Examples 2

See rose/rose2.in and rose/rose2.ans in the contestant directory.

Subtasks

For $100\%$ of the data, it is guaranteed that $1 \le n, m \le 3 \times 10^5$, $1 \le u, v \le n$, and $0 \le f \le 1$.

Special Constraint A: Each rose extends to at most one child downwards.