# 1. 题目

## 题意翻译

– $1$ $l$ $r$ $x$：将 $[l,r]$区间所有数加上 $x$
– $2$ $l$ $r$ $x$：将 $[l,r]$区间所有数改成 $x$
– $3$ $l$ $r$ $x$：输出将 $[l,r]$区间从小到大排序后的第 $x$个数是的多少 (即区间第 $x$小，数字大小相同算多次，保证 $1\leq$ $x$ $\leq$ $r-l+1$ )
– $4$ $l$ $r$ $x$ $y$：输出 $[l,r]$区间每个数字的 $x$次方的和模 $y$的值 (即 ($\sum^r_{i=l}a_i^x$) $\mod y$)

# 题解

• 有 $\frac 1 4$的概率会期望让序列变为原来的 $\frac 2 3$倍
• 有 $\frac 3 4$的概率让序列多增加两个元素（$+2$）

#include <bits/stdc++.h>

#define NS (100005)

using namespace std;

typedef long long LL;

typedef pair<LL, int> PLI;

template <typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

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

struct N
{
int l, r; LL d;
N(int a, int b, LL c) {l = a, r = b, d = c;}
};

list<N> t;

typedef list<N>::iterator itr;

void Divide(int l, int r, itr& L, itr& R)
{
L = t.begin();
while (L->r < l) L++;
if (L->l < l) t.insert(L, N(L->l, l - 1, L->d)), L->l = l;
R = L;
while (R->r < r) R++;
if (R->r > r)
{
itr tmp = R; tmp++;
t.insert(tmp, N(r + 1, R->r, R->d)), R->r = r;
}
R++;
}

void Add(int l, int r, LL x)
{
itr L, R; Divide(l, r, L, R);
while (L != R) L->d += x, L++;
}

void Modify(int l, int r, LL x)
{
itr L, R; Divide(l, r, L, R);
L->r = r, L->d = x, L++, t.erase(L, R);
}

LL Kth(int l, int r, int x)
{
static vector<PLI> srt; srt.clear();
itr L, R; Divide(l, r, L, R);
while (L != R) srt.push_back(PLI(L->d, L->r - L->l + 1)), L++;
sort(srt.begin(), srt.end());
LL res = -1; int i = 0;
while (x > 0) res = srt[i].first, x -= srt[i].second, i++;
return res;
}

LL PowSum(int l, int r, LL x, LL y)
{
itr L, R; Divide(l, r, L, R);
LL res = 0;
while (L != R)
res = (res + qpow(L->d, x, y) * ((L->r - L->l + 1) % y) % y) % y, L++;
return res;
}

int n, m;

LL seed, vmx;

LL rnd()
{
LL res = seed;
seed = (seed * 7 + 13) % 1000000007;
return res;
}

int main(int argc, char const* argv[])
{
IN(n), IN(m), IN(seed), IN(vmx);
for (LL i = 1; i <= n; i += 1) t.push_back(N(i, i, rnd() % vmx + 1));
for (LL i = 1, op, l, r, x; i <= m; i += 1)
{
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() % vmx + 1;
if (op == 1) Add(l, r, x);
else if (op == 2) Modify(l, r, x);
else if (op == 3) printf("%lld\n", Kth(l, r, x));
else if (op == 4)
printf("%lld\n", PowSum(l, r, x, rnd() % vmx + 1));
}
return 0;
}


#include <bits/stdc++.h>

#define NS (100005)

using namespace std;

typedef long long LL;

typedef pair<LL, int> PLI;

template <typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

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

struct N
{
LL l, r; mutable LL d;
N(LL a, LL b = -1, LL c = -1) {l = a, r = b, d = c;}
bool operator < (const N oth) const {return l < oth.l;}
};

set<N> t;

typedef set<N>::iterator itr;

void Split(LL x)
{
itr p = t.lower_bound(N(x));
if (p == t.end() || p->l > x) p--;
if (p->r < x) return;
if (p->l < x)
{
LL tl = p->l, tr = p->r, td = p->d;
t.erase(p), t.insert(N(tl, x - 1, td)), t.insert(N(x, tr, td));
}
}

void Divide(LL l, LL r, itr& L, itr& R)
{
Split(l), Split(r + 1);
L = t.lower_bound(N(l)), R = t.lower_bound(N(r + 1));
}

void Add(LL l, LL r, LL d)
{
itr L, R;
Divide(l, r, L, R);
while (L != R) L->d += d, L++;
}

void Modify(LL l, LL r, LL d)
{
itr L, R;
Divide(l, r, L, R), t.erase(L, R);
t.insert(N(l, r, d));
}

vector<PLI> srt;

LL Kth(LL l, LL r, LL k)
{
itr L, R; srt.clear();
Divide(l, r, L, R);
while (L != R) srt.push_back(PLI(L->d, L->r - L->l + 1)), L++;
sort(srt.begin(), srt.end());
LL res = -1;
for (LL i = 0; i < srt.size() && k > 0; i += 1)
res = srt[i].first, k -= srt[i].second;
return res;
}

LL PowSum(LL l, LL r, LL x, LL y)
{
itr L, R;
Divide(l, r, L, R);
LL res = 0;
while (L != R)
res = (res + qpow(L->d, x, y) * ((L->r - L->l + 1) % y) % y) % y, L++;
return res;
}

LL n, m, seed, vmx;

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

int main(int argc, char const* argv[])
{
IN(n), IN(m), IN(seed), IN(vmx);
for (LL i = 1; i <= n; i += 1) t.insert(N(i, i, rnd() % vmx + 1));
for (LL i = 1, op, l, r, x; i <= m; i += 1)
{
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() % vmx + 1;
if (op == 1) Add(l, r, x);
else if (op == 2) Modify(l, r, x);
else if (op == 3) printf("%lld\n", Kth(l, r, x));
else if (op == 4)
printf("%lld\n", PowSum(l, r, x, rnd() % vmx + 1));
}
return 0;
}


%%%% Orz

%%%% Orz