Description

A long time ago, there was a sequence of length $n$, initially all zeros.

Fangfangfang thought the sequence was too monotonous and planned to perform $m$ operations on it. Each operation is either a range addition or a range multiplication.

After performing some operations, Fangfangfang might also query a certain number.

However, after some operations, Fangfangfang might find that a previous operation was mistaken and needs to undo that operation. The other operations and their relative order remain unchanged.

After planning these operations, Fangfangfang immediately thought of an excellent data structure to maintain them. But he was too lazy to write the solution, so he generated $10$ random testdata and threw this problem to you.

All the testdata are random; see the generator in the hint below.

Input Format

The first line contains two integers $n, m$, the length of the sequence and the number of operations.

Each of the next $m$ lines contains $2$ or $4$ integers.

1. If the first integer is $1$, then three integers $l, r, d$ follow, meaning add $d$ to every number in the range $[l, r]$.
2. If the first integer is $2$, then three integers $l, r, d$ follow, meaning multiply every number in the range $[l, r]$ by $d$.
3. If the first integer is $3$, then one integer $p$ follows, meaning query the number at position $p$ $\bmod\ 998244353$.
4. If the first integer is $4$, then one integer $p$ follows, meaning undo the operation given on input line $p$ (guaranteed to be an addition or multiplication; no operation will be undone twice).

Output Format

For each type $3$ operation, output one line with the answer.

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

Hint

For $20\%$ of the testdata, $n, m \leq 500$, time limit $1$ s.

For $50\%$ of the testdata, $n, m \leq 30000$, time limit $1$ s.

For $100\%$ of the testdata, $1 \leq n, m \leq 150000$, $1 \le l \le r \le n$, for type $3$ operations $1 \le p \le n$, for type $4$ operations $1 \le p \le m$, $0 \leq d \leq 1073741823$ (reason shown in the data generator), time limit $4.5$ s.

Data generator:

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

Translated by ChatGPT 5