Online Ordered Set Maintenance

You are required to maintain an online sorted set \( S \) of natural numbers and support the following operations:

1. Given a number \( x \), if \( x \notin S \) then add \( x \) into \( S \).
2. Given a number \( x \), if \( x \in S \) then remove \( x \) from \( S \).
3. Query the minimum element in \( S \); if \( S=\varnothing \) then output \( -1 \).
4. Query the maximum element in \( S \); if \( S=\varnothing \) then output \( -1 \).
5. Query the number of elements in \( S \).
6. Given a number \( x \), check whether \( x \) is in \( S \); output \( 1 \) if yes, otherwise \( 0 \).
7. Given a number \( x \), let \( T=S\cap[0,x) \) (i.e. all elements strictly less than \( x \)); output the maximum element in \( T \), or \( -1 \) if \( T=\varnothing \).
8. Given a number \( x \), let \( T=S\cap[x,n) \) (i.e. all elements greater than or equal to \( x \)); output the minimum element in \( T \), or \( -1 \) if \( T=\varnothing \).

Online Parameter Modification: To prove that you are processing the operations online, for every update operation (types 1 and 2) and every query of types 6, 7, and 8 after the first query operation, the actual parameter \( x \) used is \( x = x' + \text{last} \), where \( x' \) is the parameter provided in the input and \( \text{last} \) is the return value of the most recent query. (The first query operation is one of types 3, 4, or 5, and its parameter is used as given.) It is guaranteed that \( 0 \le x < n \).

The initial set \( S \) is empty.

inputFormat

The input begins with two integers \( Q \) and \( n \) (\(1 \le Q \le 10^5\), \(1 \le n \le 10^9\)), where \( Q \) is the number of operations and \( n \) is the upper bound for elements (all elements are in the range \([0,n)\)). The following \( Q \) lines each describe an operation. Each line starts with a number representing the operation type:

• Type 1: 1 x' (add operation)
• Type 2: 2 x' (delete operation)
• Type 3: 3 (query minimum)
• Type 4: 4 (query maximum)
• Type 5: 5 (query set size)
• Type 6: 6 x' (membership query)
• Type 7: 7 x' (query maximum element less than \( x \))
• Type 8: 8 x' (query minimum element not less than \( x \))

Note that for operations of types 1, 2, 6, 7, and 8 which occur after the first query operation, the effective parameter \( x \) is computed as \( x = x' + \text{last} \), where \( \text{last} \) is the answer of the most recent query operation. For the first query, use the given parameter as is.

outputFormat

For each query operation (types 3, 4, 5, 6, 7, and 8), output the result on a separate line.

sample

12 50
3
1 5
1 6
5
2 2
6 3
1 10
7 10
8 0
4
2 0
8 10

-1
2
1
5
5
11
-1