rt,测阳历的时候疯狂RE，这个 split 一直在鬼畜，帮帮呗。（CSP考前写ODT祭）

#include<bits/stdc++.h>
#define MSEED 1000000007 
#define iter set<maintain>::iterator
#define int long long
using namespace std;
const int N=1e5+7; 
int n,q,seed,vmax,RET,a[N];
inline int rnd()
{
	RET=seed;
	seed=(seed*7+13)%MSEED;
	return RET;
}
int qpow(int x,int y,int P)
{
	int res=1;
	for(;y;y>>=1)
	{
		if(y&1)
			res=res*x%P;
		x=x*x%P;
	}
	return res;
}
struct Old_Driver_Tree
{
	struct maintain
	{
		int l,r;
		mutable int val;
		bool operator<(const maintain &e)const
		{
			return l<e.l;
		}
	};
	set<maintain> s;
	iter split(int pos)
	{
		iter it=s.lower_bound({pos,0,0});
		if(it!=s.end()&&it->l==pos)
			return it;
		it--;
		int L=it->l,R=it->r,V=it->val;
		s.erase(it);
		s.insert({L,pos-1,V});
		return s.insert({pos,R,V}).first; 
	}
	void assign(int l,int r,int v)
	{
		iter R=split(r+1),L=split(l);
		s.erase(L,R);
		s.insert({l,r,v});
		return;
	}
	void add(int l,int r,int x)
	{
		iter R=split(r+1),L=split(l);
		for(iter it=L;it!=R;it++)
		{
			it->val+=x;
		}		
		return;
	}
	int kth(int l,int r,int k)
	{
		iter R=split(r+1),L=split(l);
		vector< pair<int,int> > v;
		for(iter it=L;it!=R;it++)
		{
			v.push_back({it->val,(it->r)-(it->l)+1});
		}
		for(auto it:v)
		{
			k-=it.second;
			if(k<=0)
				return it.first;
		}
		return v[v.size()-1].first;
	}
	int query(int l,int r,int x,int y)
	{
		int res=0;
		iter R=split(r+1),L=split(l);
		for(iter it=L;it!=R;it++)
		{
			int siz=it->r-it->l+1;
			res=(res+(qpow(it->val,x,y)%y*siz%y))%y;
		}		
		return res%y;
	}
}odt;
void Debug()
{
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		odt.assign(i,i,a[i]);
	}
	while(q--)
	{
		int op,l,r,x,y;
		scanf("%lld%lld%lld%lld",&op,&l,&r,&x);
		if(op==4)
			scanf("%lld",&y);
		if(op==1)
			odt.add(l,r,x);
		else if(op==2)
			odt.assign(l,r,x);
		else if(op==3)
			printf("%lld\n",odt.kth(l,r,x));
		else if(op==4)
			printf("%lld\n",odt.query(l,r,x,y)); 
	}
	return;
}
signed main()
{
	scanf("%lld%lld%lld%lld",&n,&q,&seed,&vmax);
//	Debug();
//	return 0;
	for(int i=1;i<=n;i++)
	{
		a[i]=rnd()%vmax+1;
		odt.assign(i,i,a[i]);	
	}
	while(q--)
	{
		int op=rnd()%4+1,l=rnd()%n+1,r=rnd()%n+1,x,y;
		if(l>r)
			swap(l,r);
		if(op==3)
			x=(rnd()%(r-l+1))+1;
		else
			x=rnd()%vmax+1;
		if(op==4)
			y=rnd()%vmax+1;
		if(op==1)
			odt.add(l,r,x);
		else if(op==2)
			odt.assign(l,r,x);
		else if(op==3)
			printf("%lld\n",odt.kth(l,r,x));
		else if(op==4)
			printf("%lld\n",odt.query(l,r,x,y)); 
	}
    return 0;
}