〈 TREEのOI 2022 Spring 〉Essential Operations

最近，月球上神秘出现了一个环。 据说，只要拿到这个环，便可以穿越时空…… 

你需要维护一个 $n$ 个元素的数列 $A$ ，并执行 $m$ 个操作： - `1 l r x`：$[l,r]$ 区间全部数加 $x$； - `2 l r x`：$[l,r]$ 区间全部数乘 $x$； - `3 l r`：输出 $[l,r]$ 区间所有数的和 $S \bmod 19260817$ 的值； - `4`：$A$ 数列回溯到上一次`4`操作**前**（如果不存在上一次则回溯到初始状态），同时**倒序执行**上一次回溯后到回溯前的所有`1`操作和`2`操作（见样例解释）。

第一行两个正整数 $n,m$ 。 第二行 $n$ 个整数，代表 $A$ 的初始状态。 第 $3\sim m+2$ 行：$m$ 个操作，格式见题目描述。

对于每个 $3$ 操作，输出一个正整数后换行。

5 5
1 2 3 4 5
1 1 3 3
2 2 4 2
3 1 5
4
3 1 5

39
33

5 7
1 1 1 1 1
1 1 3 1
2 2 4 2
4
1 1 5 1
2 1 5 2
4
3 1 5

31

7 14
305 740 36 205 343 20 90 
4
2 2 7 529
3 1 2
1 2 4 713
4
3 3 7
3 2 4
4
1 6 7 597
1 1 4 232
3 2 4
1 1 3 220
3 1 7
4

391765
1121480
1650480
521784
763812

#### 样例解释： ##### 1 1. 初始状态 `1 2 3 4 5`； 2. `1 1 3 3` -> 此时数列为`4 5 6 4 5`； 3. `2 2 4 2` -> 此时数列为`4 10 12 8 5`； 4. `3 1 5` -> $ans=4+10+12+8+5=39$ 5. `4` -> 回溯到初始状态`1 2 3 4 5` -> 依次执行`2 2 4 2`与`1 1 3 3` -> 此时数列为`4 7 9 8 5`； 6. `3 1 5` -> $ans=4+7+9+8+5=33$ ##### 2 1. 初始状态 `1 1 1 1 1` 2. `1 1 3 1`: `2 2 2 1 1` 3. `2 2 4 2`: `2 4 4 2 1` 4. `4`: `2 3 3 2 1` 5. `1 1 5 1`: `3 4 4 3 2` 6. `2 1 5 2`: `6 8 8 6 4` 7. `4`: 回溯到`2 4 4 2 1`并依次执行`2 1 5 2` -> `1 1 5 1`: `5 9 9 5 3` 8. `3 1 5 2` 答案为 $31$ #### 数据范围 对于前 $10\%$ 的数据，没有 $4$ 操作。 对于前 $30\%$ 的数据，$n,m \le 10^3$。 对于前 $50\%$ 的数据，空间限制为 $400$ MB，另 $50\%$ 的数据空间限制为 $45$ MB。 对于 $100\%$ 的数据， $1 \le n \le 5 \times 10^5$，$0 \le A_i,x \le 10^3$，$1 \le m \le 10^5$ 。 d0j1a_1701 是个煽凉的出题人，所以时间限制为 $500$ ms。 --- #### 彩蛋 >  *** #### 【后记】 你穿着最新款高科技宇航服登上了月球。 那令人梦寐以求的环，就在眼前。 你缓缓走了过去。 只见环却从四周延伸出透明的屏障，里面散发出蓝绿的光芒，将你罩住。 你飞起来了！你已无法分清是你在控制环，还是环在控制你。  突然，一道刺眼的亮光照射了进来，你下意识地闭上了眼睛，耳旁呼呼地响。你感觉好像有风，但又不是普通的风。 突然，风停了。腿脚又站在了陆地上。睁开迷蒙的眼睛，你看见，rin 和 len 在玩一个绝对简单的游戏……