U645267 lyh 的挚爱（Varesa【A】）

lyh 的挚爱当然是 Varesa。 PRE 杯（#2026.1.30 Lv.1）T4（CF2100）。

lyh 为了给 Varesa 做一顿丰盛早餐，准备了足足 $n$ 种美食，包括但不限于菇菇山脉（超大份）。初始时 Varesa 对于 lyh 准备的第 $i$ 种美食有 $a_i$ 点的喜爱度，喜爱度越大就代表越喜欢。在开吃前 Varesa 想了 $T$ 秒，总共有 $m$ 个心理活动，在第 $t_i(1 \le t_i \le T)$ 秒时心理活动有且仅有以下几种，以下列形式输入，$opt$ 为种类。 - $opt = 1,\ t_i \ l_1 \ r_1 \ k(1 \le l_1 \le r_1 \le n)$，Varesa 想到了区间 $[l,r]$ 内美食的优点，她对他们**每一个**的喜爱度增加 $k$。 - $opt = 2,\ t_i \ t_{l_2} \ t_{r_2}(1 \le t_{l_2} \le t_{r_2} \lt t_i)$，Varesa 撤回了区间 $[t_{l_2},t_{r_2}]$ 内的想法。（保证区间内不会存在 $2,3,4$ 操作，对当前已被撤销的操作 $1$ 不生效） - $opt = 3,\ t_i \ t_{l_3} \ t_{r_3}(1 \le t_{l_3} \le t_{r_3} \lt t_i)$，Varesa 恢复了区间 $[t_{l_3},t_{r_3}]$ 内的想法。（保证区间内不会存在 $2,3,4$ 操作，对当前未被撤销的操作 $1$ 不生效） - $opt = 4,\ t_i$，Varesa 想知道此时她最喜爱的美食的喜爱度是多少。 由于 Varesa 很少挑食，所以 $1 \le a_i,k \le 10 ^ 3$。

第一行为 $T,n,m$。 第二行为 $a_i$。 后 $m$ 行为对应的操作。

输出若干个操作 $4$ 的结果。

| 测试点 | $n$ | $T$ | 特殊性质 | | :---: | :---: |:---:| :---: | |$1$|$\le 10$|$\le 10$|无| |$2,3$|$\le 100$|$\le 100$|$a_i$ 是升序排列的| |$4,5$|$= 1$|$\le 10 ^ 3$|无| |$6 \sim 8$|$\le 10 ^ 3$|$\le 10$|无| |$9 \sim 11$|$\le 10^3$|$\le 10 ^ 3$|没有操作 $2,3$| |$12,13$|$\le 10$|$\le 10^5$|无| |$14,15$|$\le 10 ^ 5$|$\le 10 ^ 5$|操作 $4$ 只有一个| |$16 \sim 20$|$\le 10 ^ 5$|$\le 10 ^ 5$|所有操作 $4$ 处于尾端| |$21 \sim 25$|$\le 5 \times 10 ^ 5$|$\le 5 \times 10 ^ 5$|无| 对于 $100\%$ 的数据，$1 \le n \le 5 \times 10 ^ 5$,$1 \le m \le T \le 5 \times 10 ^ 5$，保证 $t_i$不重复且单调递增，存在至少一个操作 $4$。