记录编号	607761	评测结果	AAAAAAAAAA
题目名称	3134.[Codeforces] Willem, Chtholly and Seniorious	最终得分	100
用户昵称	梦那边的美好ME	是否通过	通过
代码语言	C++	运行时间	2.877 s
提交时间	2025-10-20 15:30:48	内存使用	8.18 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ri register int
#define str set<node>::iterator

ll n,m;
ll seed,vmax;

struct node{
    ll l,r;
    mutable ll v;
    node(int L,int R=-1,ll V=0){
        l=L,r=R,v=V;
    }
    bool operator <(const node &a)const{
        return l<a.l;
    }
};

set<node> s;


str split(ll pos){
    str it=s.lower_bound(node(pos));
    if(it!=s.end()&&it->l==pos) 
        return it;
    it--;
    int l=it->l,r=it->r;
    ll v=it->v;
    s.erase(it);
    s.insert(node(l,pos-1,v));
    return s.insert(node(pos,r,v)).first;

}

void assign(ll l,ll r,ll v) {
	str it2=split(r+1),it1=split(l);
    s.erase(it1,it2);
    s.insert(node(l,r,v));
}

void add(ll l,ll r,ll val){
    str it2=split(r+1),it1=split(l);
    for(;it1!=it2;it1++)
        it1->v+=val;
}

ll rk(ll l,ll r,ll k){
    vector<pair<ll,int>> p;
    str it2=split(r+1),it1=split(l);
    p.clear();
    for(;it1!=it2;it1++)
        p.push_back(pair<ll,int>(it1->v,it1->r-it1->l+1));
    sort(p.begin(),p.end());
    for(vector<pair<ll,int>>::iterator it=p.begin();it!=p.end();it++){
        k-=it->second;
        if(k<=0) 
            return it->first;
    }
    return -1;
}

ll qpow(ll x,ll y,ll p){
    ll res=1,ans=x%p;
    while(y){
        if(y&1) 
            res=res*ans%p;
        ans=ans*ans%p;
        y>>=1;
    }
    return res;
}

ll sum(ll l,ll r,ll x,ll y){
    str it2=split(r+1),it1=split(l);
    ll res=0;
    for(;it1!=it2;it1++)
        res=(res+1ll*(it1->r-it1->l+1)*qpow(it1->v,1ll*x,1ll*y))%y;
    return res;
}

int main(){
	freopen("kdl.in","r",stdin);
	freopen("kdl.out","w",stdout);
	scanf("%lld %lld",&n,&m);
    for (int i=1;i<=n;i++){
    	ll x;
    	scanf("%lld",&x);
    	s.insert(node(i,i,x));
	}
    s.insert(node(n+1,n+1,0));
    for(ri i=1;i<=m;i++){
    	ll op,l,r,x,y;
    	scanf("%lld %lld %lld %lld",&op,&l,&r,&x);
        if(l>r) swap(l,r);
        if(op==3){
            printf("%lld\n",rk(l,r,x));
        }
        if(op==1)
            add(l,r,x);
        if(op==2)
            assign(l,r,x);
        if(op==4){
        	scanf("%lld",&y);
            printf("%lld\n",sum(l,r,x,y));
        }
    }
    return 0;
}