Dynamic Multiset Queries

You are given an initially empty multiset (M) which can contain duplicate elements. You need to perform (Q) operations on (M). The operations are described as follows:

1. Insert (x): Insert the number (x) into (M).
2. Delete (x): Remove one occurrence of the number (x) from (M) (if multiple exist, remove only one).
3. Query: Output (#{y\in M : y < x} + 1), i.e. the number of elements in (M) that are strictly less than (x), plus one.
4. Rank Query: Output the number that is at the (x)-th position in (M) when sorted in increasing order (1-indexed).
5. Predecessor Query: Output the maximum number in (M) that is strictly less than (x).
6. Successor Query: Output the minimum number in (M) that is strictly greater than (x).

Note: For operations 3, 5, and 6, it is not guaranteed that (x) exists in (M). Also, if a query (such as rank query, predecessor, or successor) cannot be answered because no valid number exists, output None.

All formulas are in (\LaTeX) format.

inputFormat

The first line contains an integer (Q) representing the number of operations. The following (Q) lines each contain two integers: the operation code and (x). The operation code is one of {1, 2, 3, 4, 5, 6} corresponding to the operations described above.

outputFormat

For each query operation (i.e. operations 3, 4, 5, and 6), output the result on a separate line. If the query cannot be answered, output None.

sample

10
1 10
1 20
1 15
3 15
4 2
5 15
6 15
2 15
4 2
3 15

2
15
10
20
20
2