题目描述

在很久很久以前，有一个长度为 $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$ 操作输出一行表示答案。

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

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$，$0 \leq p \leq 1073741823$（原因见数据生成器），时限4.5s。

数据生成器：

#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";
        }
    }
}