Problem Description

You need to maintain online a sorted set $S$ of natural numbers and support the following operations:

1. Given a number $x$, if $x$ is not in the set $S$, then insert $x$ into $S$.
2. Given a number $x$, if $x$ is already in the set $S$, then delete $x$ from $S$.

To prove that you are maintaining $S$, you must answer the following queries during the operations:

3. Output the value of the minimum element in $S$. If $S=\varnothing$, return -1.
4. Output the value of the maximum element in $S$. If $S=\varnothing$, return -1.
5. Output the number of elements in $S$.
6. Given a number $x$, determine whether $x$ is in the set. If yes, return 1; otherwise, return 0.
7. Given a number $x$, let $T=S\cap[0^-,x)$. Output the value of the maximum element in $T$. If $T=\varnothing$, return -1.
8. Given a number $x$, let $T=S\cap[x,n)$. Output the value of the minimum element in $T$. If $T=\varnothing$, return -1.

To prove that you maintain $S$ online, for all operations $1,2$ and queries $6,7,8$ after the first query, the actual parameter $x$ equals the parameter $x'$ given in the input plus the return value $\text{last}$ of the previous query. That is, $x=x'+\text{last}$.

It is guaranteed that $0\le x<n$.

Initially, $S=\varnothing$.

Input Format

The input has $(m+1)$ lines, where the meaning of $m$ is given below.

The first line contains two positive integers $n,m$, where $n$ is the upper bound of the parameter $x$ in operations and queries, and $m$ is the total number of operations and queries.
The next $m$ lines each contain one or two natural numbers, representing one operation or one query. Each line is guaranteed to be in one of the following eight forms:

1. 1 x', meaning perform operation $1$.
2. 2 x', meaning perform operation $2$.
3. 3, meaning answer query $3$.
4. 4, meaning answer query $4$.
5. 5, meaning answer query $5$.
6. 6 x', meaning answer query $6$.
7. 7 x', meaning answer query $7$.
8. 8 x', meaning answer query $8$.

Output Format

To avoid too much output, you only need to output one line with one integer, which is the sum of the return values of all queries.

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

8

Hint

Sample Explanation

The operations actually performed and the queries actually answered are as follows:

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

Therefore, the output is $0+(-1)+0+3+3+1+0+2=8$.

Constraints

For $100\%$ of the testdata, $2^{20}\le n\le2^{30}$, $2^{14}\le m\le 2^{23}$, and $0\le x<n$.

Hint

The input size of this problem is large, so a faster input method is recommended.

$0^-$ denotes a value slightly smaller than $0$, and $[0^-,x)$ guarantees that $T$ in the 7th operation is always well-defined.

Translated by ChatGPT 5