Description

You need to implement a data structure (refer to the problem title) to maintain a multiset of integers, and support the following operations for each historical version:

1. Insert $x$.

2. Delete $x$ (if there are multiple equal numbers, delete only one; if none exists, ignore this operation).

3. Query the rank of $x$ (rank is defined as the number of elements strictly less than $x$, plus $1$).

4. Query the number whose rank is $x$.

5. Query the predecessor of $x$ (the predecessor is defined as the largest number strictly less than $x$; if it does not exist, output $-2^{31}+1$).

6. Query the successor of $x$ (the successor is defined as the smallest number strictly greater than $x$; if it does not exist, output $2^{31}-1$).

Unlike the original balanced tree, every operation here is based on some historical version and produces a new version. (Operations 3, 4, 5, 6 do not modify the original version.)

Each version is numbered by the operation index (version $0$ is the initial state, an empty tree).

Input Format

The first line contains a positive integer $n$, the total number of operations.

The next $n$ lines each contain three integers. On the $i$-th line, they are $v_i, \text{opt}_i, x_i$.

$v_i$ is the index of the past version to base on, $\text{opt}_i$ is the operation type, and $x_i$ is the value involved in the operation.

Output Format

Each line contains one integer, in order, corresponding to the answers for operations $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

Hint

Constraints
For $28\%$ of the testdata, $1 \leq n \leq 10$.
For $44\%$ of the testdata, $1 \leq n \leq 2 \times 10^2$.
For $60\%$ of the testdata, $1 \leq n \leq 3 \times 10^3$.
For $84\%$ of the testdata, $1 \leq n \leq 10^5$.
For $92\%$ of the testdata, $1 \leq n \leq 2 \times 10^5$.
For $100\%$ of the testdata, $1 \leq n \leq 5 \times 10^5$, $|x_i| \leq 10^9$, $0 \le v_i < i$, $1 \le \text{opt} \le 6$.

Empirically, persistent balanced trees with normal constant factors can pass. Please rest assured.

Sample explanation:

There are $10$ operations and $11$ versions. The states of each version are:

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]$

Translated by ChatGPT 5