//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "珂朵莉树": {
        "prefix": "acm-2.10optimize",
        "body": [
            "#pragma GCC optimize(3,\"Ofast\",\"inline\")",
            "#pragma GCC optimize(2)",
            "#include<algorithm>",
            "#include<cstdio>",
            "#include<vector>",
            "#include<set>",
            "#define LL long long",
            "#define Re register int",
            "#define IT set<QAQ>::iterator",
            "using namespace std;",
            "const int N=1e5+5;",
            "struct QAQ{",
            "\tint l,r;mutable LL v;",
            "\tQAQ(int L,int R=-1,LL V=0):l(L),r(R),v(V){}",
            "\tbool operator<(QAQ o)const{return l<o.l;}",
            "};",
            "int l,r,x,y,n,m,fu,op,seed,vmax,a[N];set<QAQ>s;",
            "inline int rnd(){",
            "    Re tmp=seed;",
            "    seed=((LL)seed*7+13)%1000000007;",
            "    return tmp;",
            "}",
            "inline LL mi(LL a,LL k,LL P){",
            "\tLL ans=1;a%=P;",
            "\twhile(k){",
            "\t\tif(k&1)(ans*=a)%=P;",
            "\t\t(a*=a)%=P,k>>=1;",
            "\t}",
            "\treturn ans;",
            "}",
            "inline IT split(Re w){",
            "\tIT it=s.lower_bound(QAQ(w));",
            "\tif(it!=s.end()&&it->l==w)return it;",
            "\t--it;",
            "\tRe L=it->l,R=it->r;LL V=it->v;",
            "\ts.erase(it);",
            "\ts.insert(QAQ(L,w-1,V));",
            "\treturn s.insert(QAQ(w,R,V)).first;",
            "}",
            "inline void assign(Re l,Re r,LL v){",
            "\tIT itr=split(r+1),itl=split(l);",
            "\ts.erase(itl,itr),s.insert(QAQ(l,r,v));",
            "}",
            "inline void add(Re l,Re r,LL v){",
            "\tIT itr=split(r+1),itl=split(l);",
            "\twhile(itl!=itr)itl->v+=v,++itl;",
            "}",
            "inline LL mi_sum(Re l,Re r,Re k,Re P){",
            "\tIT itr=split(r+1),itl=split(l);LL ans=0;",
            "\twhile(itl!=itr)(ans+=(LL)(itl->r-itl->l+1)%P*mi(itl->v,(LL)k,(LL)P)%P)%=P,++itl;",
            "\treturn ans;",
            "}",
            "inline LL ask_k(Re l,Re r,Re k){",
            "\tIT itr=split(r+1),itl=split(l);",
            "\tvector<pair<LL,int> >Q;",
            "\tQ.clear();",
            "\twhile(itl!=itr)Q.push_back(pair<LL,int>(itl->v,itl->r-itl->l+1)),++itl;",
            "\tsort(Q.begin(),Q.end());",
            "\tfor(vector<pair<LL,int> >::iterator it=Q.begin();it!=Q.end();++it){",
            "\t\tk-=it->second;",
            "\t\tif(k<=0)return it->first;",
            "\t}",
            "}",
            "int main(){",
            "\tscanf(\"%d%d%d%d\",&n,&m,&seed,&vmax);",
            "\tfor(Re i=1;i<=n;++i)a[i]=(rnd()%vmax)+1,s.insert(QAQ(i,i,a[i]));",
            "\ts.insert(QAQ(n+1,n+1,0));",
            "\twhile(m--){",
            "\t    op=(rnd()%4)+1,l=(rnd()%n)+1,r=(rnd()%n)+1;",
            "\t    if(l>r)swap(l,r);",
            "\t    if(op==3)x=(rnd()%(r-l+1))+1;",
            "\t    else x=(rnd()%vmax)+1;",
            "\t    if(op==4)y=(rnd()%vmax)+1;",
            "\t    ",
            "\t    if(op<2)add(l,r,(LL)x);",
            "\t\telse if(op<3)assign(l,r,(LL)x);",
            "\t\telse if(op<4)printf(\"%lld\\n\",ask_k(l,r,x));",
            "\t\telse printf(\"%lld\\n\",mi_sum(l,r,x,y));",
            "\t}",
            "}",
            ""
        ],
        "description": "插入 珂朵莉树"
    }
}