Có $n$ chiếc xe đạp lần lượt đi vào nhà để xe; ngoại trừ chiếc đầu tiên, mỗi chiếc xe đạp sẽ đỗ đúng vào bên trái hoặc bên phải của một chiếc xe đạp nào đó đã có trong nhà xe. (Ví dụ: trong nhà xe đã có 3 chiếc xe đạp, số hiệu từ trái sang phải là: $3,5,1$. Bây giờ chiếc xe thứ 4 có số hiệu 2 muốn đỗ bên trái xe số 5, vậy số hiệu các xe trong nhà xe lúc này là: $3,2,5,1$). Cho biết tình huống đỗ xe của $n$ chiếc xe đạp, hãy in ra theo thứ tự số hiệu các xe đạp có trong nhà xe cuối cùng.

$n \leq 100000$.

Dữ liệu vào

Dòng đầu tiên là một số nguyên $n$. Dòng thứ hai là một số nguyên $x$, biểu thị số hiệu của chiếc xe đạp đầu tiên. $n-1$ dòng tiếp theo, mỗi dòng gồm 3 số nguyên $x,y,z$.

• Khi $z=0$: xe đạp số hiệu $x$ đỗ đúng bên trái xe đạp số hiệu $y$.

• Khi $z=1$: xe đạp số hiệu $x$ đỗ đúng bên phải xe đạp số hiệu $y$.

Dữ liệu ra

In ra số hiệu các xe đạp trong nhà xe theo thứ tự từ trái sang phải.

Ví dụ

Input

4
3
1 3 1
2 1 0
5 2 1

Output

3 2 5 1