题目描述

小 C 有一个队列，他要对这个队列进行 $q$ 次操作。操作共四种，参数分别如下：

$1\ x$：这是第一种操作，表示从队尾依次插入 $1,2,3,\cdots,x$；

$2\ y$：这是第二种操作，表示弹出队头的前 $y$ 个元素；

$3\ z$：这是第三种操作，表示查询队列中的第 $z$ 个元素；

$4$：这是第四种操作，表示查询队列中所有元素的最大值。

你需要帮助他维护这个队列，并对于每个第三种操作和第四种操作，输出查询的答案。

输入格式

第一行两个整数 $c,q$，其中 $c$ 表示测试点编号。$c=0$ 表示该测试点为样例。

接下来 $q$ 行，每行 $1 \sim 2$ 个整数，表示一个操作，格式见【题目描述】。

输出格式

对于每个第三种操作和第四种操作，输出一行一个整数，表示查询的答案。

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

3
2
4
1

提示

【样例解释 #1】

在进行第四次操作后，队列中的元素依次为 $3,4,5,1,2,3,1,2,3,4$。

在进行第七次操作后，队列中的元素依次为 $2,3,1,2,3,4$。

【样例 #2】

见附加文件中的 queue/queue2.in 与 queue/queue2.ans。

该样例满足测试点 $1$ 的限制。

【样例 #3】

见附加文件中的 queue/queue3.in 与 queue/queue3.ans。

该样例满足测试点 $4$ 的限制。

【样例 #4】

见附加文件中的 queue/queue4.in 与 queue/queue4.ans。

该样例满足测试点 $11$ 的限制。

【样例 #5】

见附加文件中的 queue/queue5.in 与 queue/queue5.ans。

该样例满足测试点 $15$ 的限制。

【样例 #6】

见附加文件中的 queue/queue6.in 与 queue/queue6.ans。

该样例满足测试点 $20$ 的限制。

【数据范围】

设 $\sum x$ 表示单个测试点内 $x$ 之和。

对于 $100\%$ 的数据，$1 \le q \le 2\times 10^5$，$1 \le x,y,z \le 10^9$，$0 \le \sum x \le 2\times10^{14}$，保证在进行第二种操作前队列内元素个数不小于 $y$，在进行第三种操作前队列内元素个数不小于 $z$，在进行第四种操作前队列内元素个数大于 $0$。

测试点编号	$q \le$	$x \le$	$\sum x \le$	特殊性质
$1\sim3$	$500$		$2\times10^5$	C
$4\sim8$	$5000$		$2\times10^7$	无
$9\sim10$	$2\times10^5$	$10^9$	$2\times10^{14}$	AB
$11\sim12$				B
$13\sim14$			$2\times10^9$	AC
$15\sim16$				C
$17\sim18$		$500$	$2\times10^7$	无
$19$		$10^9$	$2\times10^9$
$20$			$2\times10^{14}$

特殊性质 A：没有第二种操作。

特殊性质 B：没有第三种操作。

特殊性质 C：没有第四种操作。