题目描述

你需要在线维护一个自然数的排序集 $S$ 并支持以下操作：

1. 给一个数 $x$，若 $x$ 不在集合 $S$ 中则将 $x$ 添加到集合 $S$ 中；
2. 给一个数 $x$，若 $x$ 已在集合 $S$ 中则将 $x$ 从集合 $S$ 中删除。

为了证明你维护了 $S$，你需要在操作过程中回答以下询问：

3. 求集合 $S$ 中最小元素的值，若 $S=\varnothing$ 则返回 -1；
4. 求集合 $S$ 中最大元素的值，若 $S=\varnothing$ 则返回 -1；
5. 求集合 $S$ 中元素的数量；
6. 给一个数 $x$，判断 $x$ 是否在集合内，若在则返回 1 ，若不在则返回 0 ；
7. 给一个数 $x$，求集合 $T=S\cap[0^-,x)$ 中最大元素的值，若 $T=\varnothing$ 则返回 -1；
8. 给一个数 $x$，求集合 $T=S\cap[x,n)$ 中最小元素的值，若 $T=\varnothing$ 则返回 -1。

为了证明你在线地维护了 $S$，对于所有在第一次询问后的操作 $1,2$ 与询问 $6,7,8$，实际操作和询问的参数 $x$ 为输入中给出的操作和询问的参数 $x'$ 与上一次询问的返回结果 $\text{last}$ 之和。即 $x=x'+\text{last}$。

保证 $0\le x<n$ 。

初始时 $S=\varnothing$。

输入格式

输入共 $(m+1)$ 行，其中 $m$ 的意义见下。

第一行两个正整数 $n,m$，其中 $n$ 表示操作与询问的参数 $x$ 的上界，$m$ 表示操作与询问个数的总和。
接下来 $m$ 行，每行一个或两个自然数，表示一次操作或者询问。保证每一行为如下八种形式之一：

1. 1 x'，表示执行操作 $1$；
2. 2 x'，表示执行操作 $2$；
3. 3，表示回答询问 $3$；
4. 4，表示回答询问 $4$；
5. 5，表示回答询问 $5$；
6. 6 x'，表示回答询问 $6$；
7. 7 x'，表示回答询问 $7$；
8. 8 x'，表示回答询问 $8$。

输出格式

为避免输出过多，你只需要输出一行一个整数，表示所有询问的返回结果之和。

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

提示

样例解释

实际上执行的操作与回答的询问如下：

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

因此输出为 $0+(-1)+0+3+3+1+0+2=8$。

数据范围

对于 $100\%$ 的数据，满足 $2^{20}\le n\le2^{30},2^{14}\le m\le 2^{23},0\le x<n$。

提示

本题输入量较大，建议使用较快的读入方式。

$0^-$ 表示略小于 $0$ 的一个值，$[0^-,x)$ 可以保证第 $7$ 个操作的 $T$ 恒有意义。