https://vijos.org/records/5fa8b322f413621b7a357a5a

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;

namespace dts
{
    typedef long long ll;
    const int key=1e7+19;
    int x1[(1<<18)+1],x2[(1<<18)+1];
    class st_node
    {
        public:
            int l,r,mid;
            int x1,x2,sum=0;
            deque<int> lzctl,lzval;
            int len()
            {
                return x2-x1+1;
            }
    };
    st_node st[(1<<19)+2];
    #define lc(now) ((now)<<1)
    #define rc(now) ((now)<<1|1)
    void st_update(int now,int l,int r,int ctl,int val);
    void st_pushdown(int now)
    {
        for (;!st[now].lzctl.empty();st[now].lzctl.pop_front(),st[now].lzval.pop_front())
        {
            int ctl=st[now].lzctl.front(),val=st[now].lzval.front();
            st_update(lc(now),st[now].l,st[now].mid,ctl,val);
            st_update(rc(now),st[now].mid+1,st[now].r,ctl,val);
        }
    }
    void st_update(int now,int l,int r,int ctl,int val)
    {
        ll tmp=st[now].sum;
        if (st[now].l==l&&r==st[now].r)
        {
            if (ctl==1)
            {
                st[now].lzctl.clear(),st[now].lzval.clear();
                tmp=(ll)st[now].len()*val;
            }
            else if (ctl==2)
                tmp+=(ll)st[now].len()*val;
            else if (ctl==3)
                tmp*=(ll)val;
            if (st[now].l<st[now].r)
                st[now].lzctl.push_back(ctl),st[now].lzval.push_back(val);
        }
        else
        {
            st_pushdown(now);
            if (r<=st[now].mid)
                st_update(lc(now),l,r,ctl,val);
            else if (st[now].mid+1<=l)
                st_update(rc(now),l,r,ctl,val);
            else
                st_update(lc(now),l,st[now].mid,ctl,val),st_update(rc(now),st[now].mid+1,r,ctl,val);
            tmp=st[lc(now)].sum+st[rc(now)].sum;
        }
        st[now].sum=int((tmp%key+key)%key);
    }
    int st_ask(int now,int l,int r)
    {
        if (st[now].l==l&&r==st[now].r)
            return st[now].sum;
        else
        {
            st_pushdown(now);
            if (r<=st[now].mid)
                return st_ask(lc(now),l,r);
            else if (st[now].mid+1<=l)
                return st_ask(rc(now),l,r);
            else
                return ((st_ask(lc(now),l,st[now].mid)+st_ask(rc(now),st[now].mid+1,r))%key+key)%key;
        }
    }
    void st_build(int now,int l,int r)
    {
        st[now].l=l,st[now].r=r;
        st[now].x1=x1[l],st[now].x2=x2[r];
        st[now].lzctl.clear(),st[now].lzval.clear();
        if (l<r)
        {
            st[now].mid=(l+r)>>1;
            st_build(lc(now),l,st[now].mid);
            st_build(rc(now),st[now].mid+1,r);
        }
        st[now].sum=0;
    }
    void update(int l,int r,int ctl,int val)
    {
        if (ctl==4)
            ctl=1;
        st_update(1,l,r,ctl,val);
    }
    #define ask(l,r) st_ask(1,l,r)
    
    int n,q,t,cnt,a[(1<<7)+1],b[(1<<7)+1];
    int ctl[(1<<18)+1],pos[(1<<18)+1],val[(1<<18)+1],cmd[(1<<18)+1];
    vector<int> x;
    
    int cmp_pos(int x,int y)
    {
        return x<y;
    }
    
    int search(int pos)
    {
        int l=1,r=cnt;
        for (int mid;r-l>1;)
        {
            mid=(l+r)>>1;
            if (pos<x1[mid])
                r=mid;
            else if (pos>x1[mid])
                l=mid;
            else
                return mid;
        }
        if (x1[l]==pos)
            return l;
        else if (x1[r]==pos)
            return r;
    }
    
    void main()
    {
        scanf("%d%d",&n,&q);
        x.clear();
        for (int i=1;i<=q;i++)
        {
            scanf("%d",&ctl[i]);
            if (ctl[i]==1)
                scanf("%d%d",&pos[i],&val[i]);
            else if (2<=ctl[i]&&ctl[i]<=4)
                scanf("%d",&val[i]);
            else if (ctl[i]==5)
                scanf("%d",&pos[i]);
            if (ctl[i]==1||ctl[i]==5)
                x.push_back(pos[i]);
        }
        sort(&x[0],&x[x.size()],cmp_pos);
        int posi=1;
        cnt=0;
        for (int i=0;i<x.size();i++)
        {
            if (i>0)
                while (x[i]==x[i-1])
                    i++;
            if (i<x.size())
            {
                if (posi<=x[i]-1)
                    x1[++cnt]=posi,x2[cnt]=x[i]-1;
                x1[++cnt]=x[i],x2[cnt]=x[i];
                posi=x[i]+1;
            }
        }
        if (posi<=n)
            x1[++cnt]=posi,x2[cnt]=n;
        st_build(1,1,cnt);
        scanf("%d",&t);
        for (int i=1;i<=t;i++)
            scanf("%d%d",&a[i],&b[i]);
        int ans=0;
        for (int i=1;i<=t;i++)
        {
            for (int j=1;j<=q;j++)
                cmd[j]=(int)(((ll)a[i]+(ll)b[i]*j)%q+1);
            for (int j=1;j<=q;j++)
            {
                if (ctl[cmd[j]]==1)
                {
                    int x=search(pos[cmd[j]]);
                    update(x,x,ctl[cmd[j]],val[cmd[j]]);
                }
                else if (2<=ctl[cmd[j]]&&ctl[cmd[j]]<=4)
                    update(1,cnt,ctl[cmd[j]],val[cmd[j]]);
                else if (ctl[cmd[j]]==5)
                {
                    int x=search(pos[cmd[j]]);
                    ans=((ans+ask(x,x))%key+key)%key;
                }
                else if (ctl[cmd[j]]==6)
                    ans=((ans+ask(1,cnt))%key+key)%key;
            }
        }
        printf("%d\n",ans);
    }
}

int main()
{
    dts::main();
}