题目描述

《创建二叉搜索树》

输入一列整数，请你按顺序插入并创建二叉搜索树，之后输出中序和后序遍历序列。然后指定一个要删除的值和一个要插入的值，在完成插入和删除后输出中序和后序遍历序列。

输入格式

4行。第1行一个整数n。第2行，n个空格隔开的整数（不重复）。 第3行，一个要被删除的整数。第4行，一个要新插入的整数。

输出格式

6行。1、2行，中序和后序序列。3、4行，完成删除后的中序和后序序列。5、6行，完成插入后的中序和后序序列。

样例

输入样例 1

7
14 3 5 7 1 20 8 
8
9

输出样例 1

1 3 5 7 8 14 20
1 8 7 5 3 20 14
1 3 5 7 14 20
1 7 5 3 20 14
1 3 5 7 9 14 20
1 9 7 5 3 20 14

输入样例 2

5
5 3 7 2 4
2
6

输出样例 2

2 3 4 5 7 
2 4 3 7 5 
3 4 5 7 
4 3 7 5 
3 4 5 6 7 
4 3 6 7 5

输入样例 3

7
14 3 5 7 1 20 8 
14
4

输出样例 3

1 3 5 7 8 14 20
1 8 7 5 3 20 14
1 3 5 7 8 20
1 8 7 5 3 20
1 3 4 5 7 8 20
1 4 8 7 5 3 20

输入样例 4

3
5 3 7
5
6

输出样例 4

3 5 7 
3 7 5 
3 7 
3 7 
3 6 7 
6 3 7

输入样例 5

3
10 5 15
100
12

输出样例 5

5 10 15 
5 15 10 
5 10 15 
5 15 10 
5 10 12 15 
5 12 15 10