题目背景

本题为题目 普通平衡树 的可持久化加强版。

数据已经经过强化

感谢@Kelin 提供的一组hack数据

题目描述

您需要写一种数据结构（可参考题目标题），来维护一个可重整数集合，其中需要提供以下操作（ 对于各个以往的历史版本 ）：

1、 插入 $x$

2、 删除 $x$（若有多个相同的数，应只删除一个，如果没有请忽略该操作）

3、 查询 $x$ 的排名（排名定义为比当前数小的数的个数 $+1$）

4、查询排名为 $x$ 的数

5、 求 $x$ 的前驱（前驱定义为小于 $x$，且最大的数，如不存在输出 $-2^{31}+1$ ）

6、求 $x$ 的后继（后继定义为大于 $x$，且最小的数，如不存在输出 $2^{31}-1$ ）

和原本平衡树不同的一点是，每一次的任何操作都是基于某一个历史版本，同时生成一个新的版本。（操作3, 4, 5, 6即保持原版本无变化）

每个版本的编号即为操作的序号（版本0即为初始状态，空树）

输入格式

第一行包含一个正整数 $n$ ，表示操作的总数。

接下来 $n$ 行，每行包含三个整数，第 $i$ 行记为 $v_i, \text{opt}_i, x_i$。

$v_i$ 表示基于的过去版本号，$\text{opt}_i$ 表示操作的序号， $x_i$ 表示参与操作的数值

输出格式

每行包含一个整数，依次为各个 $3,4,5,6$ 操作所对应的答案

10
0 1 9
1 1 3
1 1 10
2 4 2
3 3 9
3 1 2
6 4 1
6 2 9
8 6 3
4 5 8

9
1
2
10
3

提示

【数据范围】
对于 $28\%$ 的数据，$1 \leq n \leq 10$；
对于 $44\%$ 的数据，$1 \leq n \leq 2\times {10}^2$；
对于 $60\%$ 的数据， $1 \leq n \leq 3\times {10}^3$；
对于 $84\%$ 的数据， $1 \leq n \leq {10}^5$；
对于 $92\%$ 的数据， $1 \leq n \leq 2\times {10}^5$；
对于 $100\%$ 的数据， $1 \leq n \leq 5 \times 10^5$ , $|x_i| \leq {10}^9$，$0 \le v_i < i$，$1\le \text{opt} \le 6$。

经实测，正常常数的可持久化平衡树均可通过，请各位放心

样例说明：

共 $10$ 次操作，$11$ 个版本，各版本的状况依次是：

0. $[]$

1. $[9]$

2. $[3, 9]$

3. $[9, 10]$

4. $[3, 9]$

5. $[9, 10]$

6. $[2, 9, 10]$

7. $[2, 9, 10]$

8. $[2, 10]$

9. $[2, 10]$

10. $[3, 9]$