Willem, Chtholly and Seniorious dfydada

#include<bits/stdc++.h>
#define mul(a,b,c) ((a)*(b)%(c))
using namespace std;
typedef long long ll;
typedef pair<int,ll> pil;
ll pow(ll a,ll b,ll m)
{
	ll r=1;
	for(a%=m; b; a=mul(a,a,m),b>>=1)
		if(b&1)r=mul(r,a,m);
	return r;
}
struct ChthollyTree:map<int,pil>
{
	iterator split(int pos)
	{
		iterator it=lower_bound(pos);
		if(it!=end()&&it->first==pos)return it;
		--it;
		if(pos>it->second.first)return end();
		pair<int,pil> p=*it;
		erase(it);
		insert(make_pair(p.first,pil(pos-1,p.second.second)));
		return insert(make_pair(pos,p.second)).first;
	}
	void add(int l,int r,ll val)
	{
		for(iterator b=split(l),e=split(r+1); b!=e; ++b)b->second.second+=val;
	}
	void set(int l,int r,ll val)
	{
		erase(split(l),split(r+1)),insert(make_pair(l,pil(r,val)));
	}
	ll rank(int l,int r,int k)
	{
		vector<pair<ll,int> > v;
		for(iterator b=split(l),e=split(r+1); b!=e; ++b)
			v.push_back(make_pair(b->second.second,b->second.first-b->first+1));
		sort(v.begin(),v.end());
		for(int i=0; i<v.size(); ++i)
			if(k-=v[i].second,k<=0)return v[i].first;
		return -1;
	}
	ll sum(int l,int r,ll ex,ll m)
	{
		ll res=0;
		for(iterator b=split(l),e=split(r+1); b!=e; ++b)
			res=(res+mul(b->second.first-b->first+1,pow(b->second.second,ex,m),m))%m;
		return res;
	}
} t;
ll n,m,seed,vmax,M=1e9+7;
ll rnd()
{
	ll ret=seed;
	seed=(seed*7+13)%M;
	return ret;
}
int main()
{
	scanf("%lld%lld%lld%lld",&n,&m,&seed,&vmax);
	for(int i=1; i<=n; ++i)
		t.insert(make_pair(i,pil(i,rnd()%vmax+1)));
	for(int i=1; i<=m; ++i)
	{
		int op=rnd()%4+1,l=rnd()%n+1,r=rnd()%n+1;
		if(l>r)swap(l,r);
		ll x=rnd()%(op==3?r-l+1:vmax)+1;
		if(op==1)t.add(l,r,x);
		if(op==2)t.set(l,r,x);
		if(op==3)printf("%lld\n",t.rank(l,r,x));
		if(op==4)printf("%lld\n",t.sum(l,r,x,rnd()%vmax+1));
	}
}