### 题解

$qhy$通过猫咪的第六感感觉这个证明有问题(我明天上文化课的时候再确认一下 qwq 最近总是不太自信)

(upd: 事实上这个证明应该是没有问题的，不过我最后的复杂度算错了 qwq，这里修正一下 (不过也就是一个常数的问题啦))

#include<bits/stdc++.h>
#define fo(i, a, b) for(int i = (a); i <= (b); ++i)
#define N 100005
#define inf 1000000005
#define ls u << 1
#define rs u << 1 | 1
#define pb push_back
int A, B, Q, n, m, data[N], id = 0;
struct node{
int p, a, b;
friend node operator + (node x, node y)
{
return (node) {std::min(x.p, y.p), 1ll * x.a * y.a % m, (1ll * x.b * y.a + y.b) % m};
}
friend bool operator < (node x, node y)
{
return x.p < y.p;
}
};
std::vector<node> q[N << 2];
inline void modify (int u, int l, int r, int L, int R, int id)
{
if (L == R)
{
if (l > 1) q[u].pb((node){l - 1, 1, 0});
q[u].pb((node){r, A, B});
if (r < n) q[u].pb((node){n, 1, 0});
return;
}
int mid = L + R >> 1;
if (id <= mid)
modify(ls, l, r, L, mid, id);
else
modify(rs, l, r, mid + 1, R, id);
if (id != R) return; //无用的更新
int p1 = 0, p2 = 0, l1 = q[ls].size() - 1, l2 = q[rs].size() - 1;
while (p1 <= l1 && p2 <= l2)
{
q[u].pb(q[ls][p1] + q[rs][p2]);
if (q[ls][p1].p == q[rs][p2].p)
{
++p1; ++p2;
}
else
{
(q[ls][p1].p < q[rs][p2].p) ? ++p1 : ++p2;
}
}
while (p1 <= l1) q[u].pb(q[ls][p1++]);
while (p2 <= l2) q[u].pb(q[rs][p2++]);
}
inline int find (int u, int pos)
{
int l = 0, r = q[u].size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (pos <= q[u][mid].p) r = mid;
else l = mid + 1;
}
return l;
}
inline node query (int u, int l, int r, int L, int R, int pos)
{
if (l <= L && R <= r)
{
return q[u][find(u, pos)];
}
node ret = (node) {pos, 1, 0};
int mid = L + R >> 1;
if (l <= mid) ret = ret + query(ls, l, r, L, mid, pos);
if (mid < r) ret = ret + query(rs, l, r, mid + 1, R, pos);
return ret;
}
int main ()
{
int T;
scanf("%d", &T); T = T & 1;
scanf("%d %d", &n, &m);
fo (i, 1, n) scanf("%d", &data[i]);
scanf("%d", &Q);
int opt, l, r, ans = 0;
node now;
while (Q--)
{
scanf("%d %d %d %d", &opt, &l, &r, &A);
if (T) {l ^= ans; r ^= ans;}
if (opt == 1)
{
scanf("%d", &B);
++id;
modify(1, l, r, 1, N, id);
}
else
{
if (T) A ^= ans;
now = query(1, l, r, 1, N, A);
ans = (1ll * data[A] * now.a + now.b) % m;
printf("%d\n", ans);
}
}
return 0;
}