Persistent Multiset Queries

You are given a persistent multiset which supports the following operations on any historical version of the multiset. Initially (version 0), the multiset is empty. Each operation is applied to some historical version v and creates a new version whose number is the current operation index.

The operations are defined as follows (using \( x \) to denote a number):

1. Insert \( x \) : Insert the number \( x \) into the multiset.
2. Delete \( x \) : Delete one occurrence of \( x \) from the multiset. If \( x \) does not exist in the version you are operating on, simply ignore this operation.
3. Query Rank of \( x \) : The rank is defined as the number of elements smaller than \( x \) plus one. (i.e. \( \text{rank}(x)=\#\{y: y < x\}+1 \))
4. Query by Rank : Given a rank \( x \) (1-indexed), return the number whose rank is \( x \) in the multiset.
5. Query Predecessor of \( x \) : The predecessor is defined as the largest number strictly less than \( x \). If no such number exists, output \( -2^{31}+1 \).
6. Query Successor of \( x \) : The successor is defined as the smallest number strictly greater than \( x \). If no such number exists, output \( 2^{31}-1 \).

Note that for the query operations (operations 3, 4, 5, 6), the underlying version remains unchanged, but a new version is still created (as a copy of the historical version). The version number of each operation equals the operation’s sequence number, starting at 1 (with version 0 being the initial empty multiset).

Input Format:

The first line contains a single integer \( n \) representing the number of operations. Each of the following \( n \) lines contains three space-separated values: \( v \), \( op \), and \( x \). Here \( v \) is the version number from which the operation is applied, \( op \) is the operation code where:

• 1: Insert
• 2: Delete
• 3: Query Rank
• 4: Query by Rank
• 5: Query Predecessor
• 6: Query Successor

Output Format:

For each query operation (operations 3, 4, 5, 6), output the result on a new line.

Note: For deletion operations, if the number \( x \) does not exist in the chosen version, simply ignore the deletion.

inputFormat

The first line contains an integer \( n \) indicating the number of operations. The next \( n \) lines each contain three space-separated values \( v \), \( op \), and \( x \):

• \( v \): the version number on which the operation is based.
• \( op \): an integer from 1 to 6 describing the operation type.
• \( x \): the parameter for the operation (its meaning depends on \( op \)).

Version 0 is the initial empty multiset. For each operation, a new version is created with its version number equal to the operation's index (starting from 1).

outputFormat

Output the answer (one per line) for each query operation (i.e. operations 3, 4, 5, 6) in the order they appear.

sample

8
0 1 5
1 1 3
2 3 3
2 4 2
2 5 5
2 6 3
2 2 3
7 3 5

1
5
3
5
1

</p>