题目描述

小蓝是一个热爱编程的图书管理员。他管理的图书馆里有一批书籍，每本书都有一个唯一的编号（正整数）。为了方便查找和整理，小蓝决定用二叉搜索树（Binary Search Tree, BST） 来维护这些编号。BST 满足：对于任意一个节点，其左子树中所有节点的编号都小于该节点，右子树中所有节点的编号都大于该节点。

初始时，树为空。小蓝需要执行一系列操作来管理书籍：

• 插入（I x）：将编号为 $x$ 的书加入树中。如果 $x$ 已存在，则忽略（不重复插入）。
• 删除（D x）：将编号为 $x$ 的书从树中移除。删除时，如果该节点有两个孩子，则用其中序前驱（即左子树中的最大值）来替代它，然后删除前驱节点；如果只有一个孩子或没有孩子，则直接删除。
• 修改（M x y）：将编号 $x$ 的书籍改为编号 $y$。操作规则：只有当 $x$ 存在且 $y$ 不存在时，才先删除 $x$，再插入 $y$；否则忽略该操作。
• 查询（Q）：小蓝需要知道当前所有书籍编号的升序排列（即中序遍历结果），以及这棵树的高度（根节点高度为 $1$，空树高度为 $0$）。

现在，给你一系列操作，请你在每次查询时输出所需信息，并在所有操作结束后（实际上查询后程序输出）输出最终状态。

输入格式

第一行包含一个正整数 $m$（$1 \le m \le 10^3$），表示操作总数。
接下来 $m$ 行，每行一个操作，格式如下：

• I x：插入整数 $x$（$1 \le x \le 10^9$）
• D x：删除整数 $x$（$1 \le x \le 10^9$）
• M x y：修改编号 $x$ 为 $y$（$1 \le x, y \le 10^9$）
• Q：查询当前树的中序遍历序列及高度

输出格式

对于每个 Q 操作，输出两行：

• 第一行：当前树的中序遍历序列，整数之间用空格分隔。若树为空，则输出一个空行。
• 第二行：一个整数，表示树的高度（根节点高度为 $1$）。

注意：题目不要求最后单独输出，所有 Q 操作的结果依次输出即可。

输入输出样例

9
I 5
I 3
I 8
I 2
I 4
D 3
M 8 6
I 7
Q

2 4 5 6 7
3

6
I 10
I 5
I 15
M 5 12
D 10
Q

12 15
2

说明/提示

操作详解

1. 插入（I）
   从根节点开始，若待插入值小于当前节点值，则向左走；若大于，则向右走。遇到空位置则插入新节点；若值已存在，则不做任何事。

2. 删除（D）
   找到待删节点 del。

   • 若 del 没有左孩子或没有右孩子（即至少一个孩子为空），则直接用其非空孩子（若存在）替代 del 的位置；若 del 是叶子，则直接移除。
   • 若 del 左右孩子均存在，则找到 del 左子树中的最大值节点（即中序前驱 pred），将 pred 的值复制给 del，然后删除 pred（删除时 pred 必无右孩子，可能有左孩子，按上述规则删除即可）。

3. 修改（M）
   先检查 $x$ 是否存在且 $y$ 是否不存在。若满足，则执行 D x 再执行 I y。否则忽略。注意，若 $x == y$，也视为忽略。

4. 查询（Q）

   • 中序遍历：递归地按“左-根-右”的顺序访问所有节点，结果即为编号的升序序列。
   • 高度：根节点高度为 $1$，空树高度为 $0$。树的高度等于从根到最远叶子节点经过的边数加一，也可以理解为最大层数。

样例 1 详解

我们一步一步构造：

1. I 5 → 树：5（根）
2. I 3 → 5 的左孩子为 3
3. I 8 → 5 的右孩子为 8
4. I 2 → 3 的左孩子为 2
5. I 4 → 3 的右孩子为 4 此时树结构：

       5
      / \
     3   8
    / \
   2   4
   

6. D 3：待删节点 3 有两个孩子（左 2，右 4）。找前驱：左子树最大值是 2（2 无右子）。将 2 的值复制到 3 的位置，然后删除原 2。树变为：

       5
      / \
     2   8
      \
       4
   

   （注意 3 节点现在值为 2，其左孩子为空，右孩子为 4）
7. M 8 6：检查 8 存在且 6 不存在 → 删除 8，插入 6。删除 8 时，8 是叶子，直接移除；插入 6 时，由于 6 > 5，应到右子树，此时右子树为空，所以 6 成为 5 的右孩子。树变为：

       5
      / \
     2   6
      \
       4
   

8. I 7：插入 7，从根 5 开始，向右到 6，再向右，插入 7 作为 6 的右孩子。树：

       5
      / \
     2   6
      \   \
       4   7
   

9. Q：中序遍历：先左子树 2 → 访问 2，然后右孩子 4，再根 5，然后右子树 6，然后 7 → 序列：2 4 5 6 7。高度：根 5 层 $1$，2 和 6 层 $2$，4 和 7 层 $3$，所以高度为 $3$。

样例 2 详解

1. I 10 → 根 10
2. I 5 → 10 左 5
3. I 15 → 10 右 15
4. M 5 12：5 存在，12 不存在 → 删除 5（叶子），插入 12。插入 12 时，从根 10 出发，12 > 10 向右到 15，再向左（空）插入，所以 12 成为 15 的左孩子。树：

       10
         \
          15
         /
       12
   

5. D 10：删除根 10，它只有右孩子 15，直接用 15 替代根。树：

       15
      /
    12
   

6. Q：中序为 12 15，高度为 $2$（根 15 层 $1$，12 层 $2$）。

数据范围与注意事项

• 对于 $100\%$ 的数据：
  • $1 \le m \le 10^3$
  • $1 \le x, y \le 10^9$