# 保留形状的二叉搜索树

预估时间限制：0.5 秒。内存限制：128 MB。

实际时限以标准程序在目标环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

档案馆用二叉搜索树整理带整数编号的条目。管理员不仅要更新条目数量，还要按规定保留树形，随时打印当前的检索结构。

(本故事由GPT-6重写)

## 形式化问题描述

维护一棵初始为空的二叉搜索树。每个结点保存一个整数键值和一个正的出现次数；其左子树键值严格较小，右子树键值严格较大。

- 插入键值：从根按大小查找。若已存在，次数加一；否则在查找所到达的空孩子位置建立结点，次数为一。不得旋转或重建树形。
- 删除键值：若不存在则忽略；否则次数减一。只有次数变为零时才物理删除结点。
- 打印：按“根、左子树、右子树”的前序顺序输出键值，每个结点只输出一次。

物理删除严格遵循以下规则：没有孩子时直接移除；只有一个孩子时由该孩子接替；有两个孩子时，将该结点的数据（键值与次数）和其中序直接后继的数据交换，然后删除后继所在的物理结点。直接后继是右子树中的最小键值结点，它没有左孩子，因此只需按前两种情况删除。数据交换不交换父子连接。

## 输入格式

第一行一个整数 $M$ .接下来 $M$ 行，每行一种操作：`0` 表示打印；`1 x` 表示插入键值 $x$ ；`2 x` 表示删除键值 $x$ .

## 输出格式

每次打印输出一行，键值之间用一个空格分隔。出现次数不影响打印次数，也不输出计数。空树输出一个空行。

## 样例

### 样例 1

### 输入

```text
20
0
1 5
1 5
1 7
1 3
1 3
2 3
0
2 5
0
2 5
0
2 7
0
2 3
0
2 3
0
1 3
0
```

### 输出

```text

5 3 7
5 3 7
7 3
3


3
```

### 样例 2

### 输入

```text
11
1 4
1 2
1 7
1 5
1 5
1 6
2 4
0
2 5
0
0
```

### 输出

```text
5 2 7 6
5 2 7 6
5 2 7 6
```

### 样例 3

### 输入

```text
6
1 -2147483648
1 2147483647
2 0
0
2 -2147483648
0
```

### 输出

```text
-2147483648 2147483647
2147483647
```

## 样例解释

样例一共有八行输出：第一、六、七行为空。重复的键值仍只打印一次；两次删除五才会物理删除根。样例二删除根四时，要把后继五的出现次数二一并移到根，随后删除一次五仍不会移除该结点。样例三包含有符号三十二位整数的两个端点。

## 数据范围与保证

$0\le M\le10^5$ , $-2^{31}\le x\le2^{31}-1$ . 打印操作不超过十次。保证不会频繁访问较深的结点；不指定数值形式的树高上限。

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |