题目背景

最近，月球上神秘出现了一个环。

据说，只要拿到这个环，便可以穿越时空……

题目描述

你需要维护一个 $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 在玩一个绝对简单的游戏……