时间限制： 1.0 秒

空间限制： 256 MB

题目描述

在二叉搜索树当中，如果所有节点的关键码互异，则有（若存在）右子节点关键码大于当前节点，（若存在）左子节点关键码小于当前节点的性质。

在本题中，给定长度为 $n$ 的关键码插入序列，你需要在一个初始为空的朴素二叉搜索树中依次插入这些关键码（即不需要做旋转等对于拓扑结构的等价变换）。并给出二叉搜索树的前序、中序、后序、层次遍历序列。

输入格式

从标准输入读入数据。

第一行包含一个整数 $n$，为插入序列长度。

第二行包含 $n$ 个不同的整数，表示每个插入值。

输出格式

输出到标准输出。

输出四行，每行 $n$ 个整数，每行相邻两个整数间用一个空格分隔。四行从上到下分别为最终二叉搜索树的前序、中序、后序、层次遍历序列。

5
1 6 5 9 8

1 6 5 9 8 
1 5 6 8 9 
5 8 9 6 1
1 6 5 9 8

样例 1 解释

二叉搜索树的最终形态见下图。

子任务

对于所有数据，插入序列长度 $n\le 10^4$，所有关键码保证 $-10^9\le a_i\le 10^9$。

本题无数据梯度，需要通过全部数据获得所有分数。