题目描述

对于给定的二叉树，你需要维护：

$\texttt{1.}\,$二叉树的先序遍历；
$\texttt{2.}\,$二叉树的中序遍历；
$\texttt{3.}\,$二叉树的后序遍历；
$\texttt{4.}\,$二叉树的层序遍历。

由于输出数据过多，请使用较快的 IO 方式！

输入格式

第一行输入一个整数 $n\left(1\leq n\leq 5 \times 10^5\right)$ 代表二叉树的节点数量。

此后 $n-1$ 行，每行输入三个整数 $u, v, op \left(1\leq u, v\leq n; 0 \leq op \leq 1 \right)$ 代表当前节点 $u$ 的父节点为 $v$ ，其中 $op = 0$ 代表当前节点是父节点的左儿子，$op = 1$ 代表当前节点是父节点的右儿子。

输出格式

在第一行上输出 $n$ 个整数，代表二叉树的先序遍历；

在第二行上输出 $n$ 个整数，代表二叉树的中序遍历；

在第三行上输出 $n$ 个整数，代表二叉树的后序遍历；

在第四行上输出 $n$ 个整数，代表二叉树的层序遍历。

输入样例

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

输出样例

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

说明/提示

在这个样例中，所构建的二叉树如下图所示：