https://codeforces.com/problemset/problem/896/C
set珂朵莉树有点长了，不太好写， 留个map珂朵莉树参考。
在map中，key用来存储区间，每一个key都是区间的左端点，value则为值。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<PII, int> PIII;
const int N = 1e5 + 5, M = 15, INF = 0x3f3f3f3f, mod = 998244353;
int n, m, seed, vmax;
int a[N];

map<int, LL> mp;

void split(int pos){
    auto it = prev(mp.upper_bound(pos));
    mp[pos] = it -> second;
}

void assign(int l, int r, LL v){
    split(r + 1);split(l);

    auto it = mp.find(l);
    while(it -> first != r + 1){
        it = mp.erase(it);
    }
    mp[l] = v;
}

void add(int l, int r, LL v){
    split(r + 1);split(l);

    auto it = mp.find(l);
    while(it -> first != r + 1){
        it -> second += v;
        it = next(it);
    }
}

struct Rnk{
    LL val, cnt;
    Rnk(LL val, LL cnt):val(val), cnt(cnt) {}

    bool operator < (const Rnk& b){
        return val < b.val;
    }
};

void kth(int l, int r, LL x){
    split(r + 1);split(l);

    vector<Rnk> rnk;
    auto it = mp.find(l);
    while(it -> first != r + 1){
        rnk.push_back(Rnk(it -> second, next(it) -> first - it -> first));
        it = next(it);
    }

    sort(rnk.begin(), rnk.end());
    for(auto y: rnk){
        x -= y.cnt;
        if(x <= 0){
            cout << y.val << "\n";
            return ;
        }
    }
}

LL qmi(LL a, LL b, LL c){
    LL res = 1;
    a %= c;
    while(b){
        if(b & 1) res = (res * a) % c;
        a = (a * a) % c;
        b >>= 1;
    }
    return res;
}

void sum(int l, int r, LL x, LL y){
    split(r + 1);split(l);

    LL sum = 0;

    auto it = mp.find(l);
    while(it -> first != r + 1){
        sum = (sum + (qmi(it -> second, x, y) * (next(it) -> first - it -> first) % y)) % y;

        it = next(it);
    }

    cout << sum << "\n";
}

int rnd(){
    int ret = seed;
    seed = (1ll * seed * 7 + 13) % 1000000007;
    return ret;
}

void solve(){
    cin >> n >> m >> seed >> vmax;

    for(int i = 1; i <= n; i++) a[i] = (rnd() % vmax) + 1, mp[i] = a[i];
    for(int i = 1; i <= m; i++){
        int op, l, r, x, y;
        op = (rnd() % 4) + 1;
        l = (rnd() % n) + 1;
        r = (rnd() % n) + 1;

        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){
            add(l, r, x);
        }
        else if(op == 2){
            assign(l, r, x);
        }
        else if(op == 3){
            kth(l, r, x);
        }
        else if(op == 4){
            sum(l, r, x, y);
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    /*int t; cin >> t;
    while(t--){
        solve();
    }*/
    return 0;
}