方方方的数据结构
题目描述
在很久很久以前，有一个长度为 $n$ 的数列，一开始数列全是 $0$。
方方方觉得这个数列太单调了，打算对它进行 $m$ 次操作，每次操作为区间加法或者区间乘法。
方方方进行一些操作之后，还可能会对某个数进行询问。
但是进行过一些操作之后，方方方可能会发现之前某次操作失误了，需要撤销这次操作，其它操作和其它操作的前后顺序保持不变。
方方方想好这些操作之后，马上想到了一个优秀的数据结构可以维护这些东西，可是他懒得写标程了，就生成了 $10$ 个**随机数据**，就把这道题扔给了你。
**数据全是随机的，生成方式见最下方的提示。**
输入输出格式
输入格式
第一行两个数 $n,m$，表示数列的长度和操作个数。
接下来 $m$ 行每行 $2$ 或 $4$ 个数。
1. 如果第一个数为 $1$，接下来跟三个数 $l,r,d$，表示把区间 $[l,r]$ 中的数加上 $d$。
2. 如果第一个数为 $2$，接下来跟三个数 $l,r,d$，表示把区间 $[l,r]$ 中的数乘上 $d$。
3. 如果第一个数为 $3$，接下来跟一个数 $p$，表示询问 $p$ 位置的数 $\bmod\ 998244353$。
4. 如果第一个数为 $4$，接下来跟一个数 $p$，表示将第 $p$ 行输入的操作撤销（保证为加或者乘操作，一个操作不会被撤销两次）。
输出格式
对于每个 $3$ 操作输出一行表示答案。
输入输出样例
输入样例 #1
6 14
1 1 5 1
2 2 4 3
1 2 6 5
3 2
4 1
3 3
2 1 3 4
3 3
1 2 2 3
3 2
4 7
3 1
3 2
3 3输出样例 #1
8
5
20
23
0
8
5说明
对于 $20\%$ 的数据，$n,m \leq 500$，时限 1s。
对于 $50\%$ 的数据，$n,m \leq 30000$，时限 1s。
对于 $100\%$ 的数据，$1 \leq n,m \leq 150000$，$1 \le l \le r \le n$，$3$ 操作的 $p$ 满足 $1 \le p \le n$，$4$ 操作的 $p$ 满足 $1 \le p \le m$，$0 \leq d \leq 1073741823$（原因见数据生成器），时限 4.5s。
数据生成器：
```cpp
#include <bits/stdc++.h>
using namespace std;
int rand_() {return rand()&32767;}
int br() {return rand_()*32768+rand_();}
vector<int> cs;
int main()
{
srand(...); //这里要填一个种子
int n=...,m=...; //这里要填n、m
cout<<n<<" "<<m<<"\n";
for(int i=1;i<=m;i++)
{
int o=rand()%4+1;
if(o<=2)
{
cout<<o<<" ";
int l=br()%n+1,r=br()%n+1;
if(l>r) swap(l,r); cs.push_back(i);
cout<<l<<" "<<r<<" "<<br()<<"\n";
}
else if(o==3) cout<<o<<" "<<br()%n+1<<"\n";
else
{
if(!cs.size()) {--i; continue;}
int s=br()%cs.size(),g=cs[s];
cs.erase(cs.begin()+s);
cout<<o<<" "<<g<<"\n";
}
}
}
```