{"raw_statement":[{"iden":"background","content":"最近，月球上神秘出现了一个环。\n\n据说，只要拿到这个环，便可以穿越时空……\n\n![](https://tse1-mm.cn.bing.net/th/id/R-C.a57722cfcdec7e164113680dbf6a0403?rik=eVL5ObGthJQrqw&riu=http%3a%2f%2fimg2.diglog.com%2fimg%2f2021%2f1%2f79df8c71177d1b9035a179506645955b.jpg&ehk=yzECJQeeeiBu9KQrax2R7VjKNVzhg2XI1z0ykNOEx2g%3d&risl=&pid=ImgRaw&r=0)"},{"iden":"statement","content":"你需要维护一个 $n$ 个元素的数列 $A$ ，并执行 $m$ 个操作：\n\n- `1 l r x`：$[l,r]$ 区间全部数加 $x$；\n\n- `2 l r x`：$[l,r]$ 区间全部数乘 $x$；\n\n- `3 l r`：输出 $[l,r]$ 区间所有数的和 $S \\bmod 19260817$ 的值；\n\n- `4`：$A$ 数列回溯到上一次`4`操作**前**（如果不存在上一次则回溯到初始状态），同时**倒序执行**上一次回溯后到回溯前的所有`1`操作和`2`操作（见样例解释）。"},{"iden":"input","content":"第一行两个正整数 $n,m$ 。\n\n第二行 $n$ 个整数，代表 $A$ 的初始状态。\n\n第 $3\\sim m+2$ 行：$m$ 个操作，格式见题目描述。"},{"iden":"output","content":"对于每个 $3$ 操作，输出一个正整数后换行。"},{"iden":"note","content":"#### 样例解释：\n\n##### 1\n\n1. 初始状态 `1 2 3 4 5`；\n2. `1 1 3 3` -> 此时数列为`4 5 6 4 5`；\n3. `2 2 4 2` -> 此时数列为`4 10 12 8 5`；\n4. `3 1 5` -> $ans=4+10+12+8+5=39$\n5. `4` -> 回溯到初始状态`1 2 3 4 5` -> 依次执行`2 2 4 2`与`1 1 3 3` -> 此时数列为`4 7 9 8 5`；\n6. `3 1 5` -> $ans=4+7+9+8+5=33$\n\n##### 2\n\n1. 初始状态 `1 1 1 1 1`\n2. `1 1 3 1`: `2 2 2 1 1`\n3. `2 2 4 2`: `2 4 4 2 1`\n4. `4`: `2 3 3 2 1`\n5. `1 1 5 1`: `3 4 4 3 2`\n6. `2 1 5 2`: `6 8 8 6 4`\n7. `4`: 回溯到`2 4 4 2 1`并依次执行`2 1 5 2` -> `1 1 5 1`: `5 9 9 5 3`\n8. `3 1 5 2` 答案为 $31$\n\n#### 数据范围\n\n对于前 $10\\%$ 的数据，没有 $4$ 操作。\n\n对于前 $30\\%$ 的数据，$n,m \\le 10^3$。\n\n对于前 $50\\%$ 的数据，空间限制为 $400$ MB，另 $50\\%$ 的数据空间限制为 $45$ MB。\n\n对于 $100\\%$ 的数据， $1 \\le n \\le 5 \\times 10^5$，$0 \\le A_i,x \\le 10^3$，$1 \\le m \\le 10^5$ 。\n\nd0j1a_1701 是个煽凉的出题人，所以时间限制为 $500$ ms。\n\n---\n\n#### 彩蛋\n\n\n> ![](https://cdn.luogu.com.cn/upload/image_hosting/d4pi6qm9.png)\n\n\n***\n\n#### 【后记】\n\n你穿着最新款高科技宇航服登上了月球。\n\n那令人梦寐以求的环，就在眼前。\n\n你缓缓走了过去。\n\n只见环却从四周延伸出透明的屏障，里面散发出蓝绿的光芒，将你罩住。\n\n你飞起来了！你已无法分清是你在控制环，还是环在控制你。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/cy4fudx3.png)\n\n突然，一道刺眼的亮光照射了进来，你下意识地闭上了眼睛，耳旁呼呼地响。你感觉好像有风，但又不是普通的风。\n\n突然，风停了。腿脚又站在了陆地上。睁开迷蒙的眼睛，你看见，rin 和 len 在玩一个绝对简单的游戏……"}],"translated_statement":null,"sample_group":[["5 5\n1 2 3 4 5\n1 1 3 3\n2 2 4 2\n3 1 5\n4\n3 1 5","39\n33"],["5 7\n1 1 1 1 1\n1 1 3 1\n2 2 4 2\n4\n1 1 5 1\n2 1 5 2\n4\n3 1 5","31"],["7 14\n305 740 36 205 343 20 90 \n4\n2 2 7 529\n3 1 2\n1 2 4 713\n4\n3 3 7\n3 2 4\n4\n1 6 7 597\n1 1 4 232\n3 2 4\n1 1 3 220\n3 1 7\n4","391765\n1121480\n1650480\n521784\n763812"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}