#1355. 终极数据结构(0=w=0〃)

终于到了小学期的最后一次作业了，为了考验你对小学期的知识的掌握程度，我们决定在最后出一道终极的数据结构测试大家的代码能力。

你需要维护一个大小为 $n$ 的int范围内的自然数数组 $A$ （下标 $[1,n]$ ），$A$ 的全部元素一开始均为 $0$。

然后你需要维护 $A$ 以支持以下询问的操作：

• 0 x y 输出 $[x,y]$ 区间的和；
• 1 x y 输出 $[x,y]$ 区间的最大值；
• 2 x y 输出 $[x,y]$ 区间的最小值；
• 3 x y 输出 $[x,y]$ 区间的中位数（区间大小偶数则为中间两项的平均值）；
• 4 x y 输出 $[x,y]$ 区间没有出现的最小的自然数；
• 5 x y z 将 $[x,y]$ 区间的值全部改为 $z$；
• 6 x y z 将 $[x,y]$ 区间所有最大值所在下标位置的值改为 $z$；
• 7 x y z 将 $[x,y]$ 区间所有最小值所在下标位置的值改为 $z$；
• 8 x 将数组恢复至 $x$ 次询问之前的状态（输出也算一次询问）。

第一行两个数 $n,q$ 代表数组的大小和询问次数；

接下来 $q$ 行，每一行开头一个数 $w$ 代表询问的类型，然后根据所进行的操作继续读取若干个数，保证操作合法不会越界或者溢出。

如果 $w\in \{0,1,2,3,4\}$，则需要按照要求输出一行一个数，表示询问结果。

样例输入

5 1
0 1 2

样例输出

0

$1\le n,q \le 10^5$

$0 \le z \le 2^{31}-1$，保证所有操作都不会使数组内有数据超过int的存储范围，也不会变成负数（$[0,2^{31}-1]$）

$0=w=0$