Codeforces896C Willem, Chtholly and Seniorious

这题我不会，，存个代码，，，

珂朵莉树

真神奇

//By AcerMo
#include<set>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define TAT set<poi>::iterator
using namespace std;
typedef long long int lli;
const int m1=1e9+7;
const int M=200050;
int n,m;
lli sed,mx,a[M];
struct poi
{
	int l,r;
	mutable lli v;
	poi(int L,int R=-1,lli val=0):l(L),r(R),v(val){}
	bool friend operator < (poi a,poi b)
	{return a.l<b.l;}
};
set<poi>s;
lli fpow(lli a, lli b, lli mod)
{
    lli z=1;a%=mod;
    for (;b;a=(a*a)%mod,b>>=1)
    if (b&1) z=(z*a)%mod;
    return z;
}
inline TAT split(int p)
{
	TAT it=s.lower_bound(poi(p));
	if (it!=s.end()&&it->l==p) return it;
	--it;int L=it->l,R=it->r;lli val=it->v;
	s.erase(it);s.insert(poi(L,p-1,val));
	return s.insert(poi(p,R,val)).first;
} 
inline void add(int l,int r,lli val=1)
{
	TAT lit=split(l),rit=split(r+1);
	for (;lit!=rit;++lit) lit->v+=val;
	return ;
}
inline void assign(int l,int r,lli val=0)
{
	TAT lit=split(l),rit=split(r+1);
	s.erase(lit,rit);
	s.insert(poi(l,r,val));
	return ;
}
inline lli qrk(int l,int r,int k)
{
	vector<pair<lli,int> >nv;nv.clear();
	TAT lit=split(l),rit=split(r+1);
	for (;lit!=rit;++lit)
	nv.push_back(pair<lli,int>(lit->v,lit->r - lit->l +1));
	sort(nv.begin(),nv.end());
	vector<pair<lli,int> >::iterator it;
	for (it=nv.begin();it!=nv.end();++it)
	{
		k-=it->second;
		if (k<=0) return it->first;
	}
	return -1LL;
}
inline lli sum(int l,int r,int e,int mod)
{
	TAT lit=split(l),rit=split(r+1);lli ans=0;
	for (;lit!=rit;lit++)
	ans=(ans+1LL*(lit->r - lit->l +1)*fpow(lit->v,lli(e),lli(mod)))%mod;
	return ans;
}
inline lli srd()
{
	lli rd=sed;
	sed=(sed*7+13)%m1;
	return rd;
}
inline void write(lli x)
{
	if (x>9) write(x/10);
	putchar(x%10+'0');
	return ;
}
signed main()
{
	cin>>n>>m>>sed>>mx;
	for (int i=1;i<=n;i++)
	{
		a[i]=(srd()%mx)+1;
		s.insert(poi(i,i,a[i]));
	}
	s.insert(poi(n+1,n+1,0));
	while (m--)
	{
		int fl=srd()%4+1;
		int l=srd()%n+1,x;
		int r=srd()%n+1,y;
		if (l>r) swap(l,r);
		if (fl==3) x=srd()%(r-l+1)+1;
		else x=srd()%mx+1;
		if (fl==4) y=srd()%mx+1;
		if (fl==1) add(l,r,1LL*x);
		else if (fl==2) assign(l,r,1LL*x);
		else if (fl==3) write(qrk(l,r,x)),puts("");
		else if (fl==4) write(sum(l,r,x,y)),puts("");
	}	
	return 0;
}