U535960 【模板】撤销RMQ

模板题，无背景。

已知一个数列 $\{a_i\}$，你需要进行下面三种操作： 1. 将某区间每一个数对 $x $ 取 $\max$。 2. 求出某区间所有数的 $\max$。 3. 撤销某一个 1 操作。 **请注意本题的空间限制。**

第一行包含两个整数 $n, m$，分别表示该数列数字的个数和操作的总个数。 第二行包含 $n$ 个用空格分隔的整数 $a_i$，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。 接下来 $m$ 行每行包含 $2-4$ 个整数，表示一个操作，具体如下： 1. `1 l r x`：将区间 $[l,r]$ 内每个数对 $x $ 取 $\max$。 2. `2 l r`：输出区间 $[l, r]$ 内所有数的 $\max$。 3. `3 x`：撤销第 $x$ 次操作。特别地，保证该操作为 1 操作，且每个 1 操作只会被撤销 1 次。

输出包含若干行整数，即所有操作 2 的结果。

对于 $30\%$ 的数据：$1 \le n,m \le {10}^4$。 对于 $60\%$ 的数据：$1 \le n,m \le {10}^5$。 对于 $100\%$ 的数据：$1 \le n, m \le 3 \times{10}^5$，输入中不存在非正数，所有数都在合理的范围内且不超过 `int` 上限。