qwq
#include <stdio.h>
#ifdef ONLINE_JUDGE
#define debug(...)
#else
#define debug(...) printf(__VA_ARGS__)
#endif
#define ls segtree[lson(i)]
#define rs segtree[rson(i)]
#define u segtree[i]
typedef long long ll;
const int SIZE = 1e5 + 5;
int a[SIZE];
int MOD;
struct node
{
int l, r;
ll sum, lazy_add, lazy_times;
}
segtree[6 * SIZE];
inline int lson(int i){return i << 1; }
inline int rson(int i){return i << 1 | 1; }
void pushup(int i)
{
debug("pushup(%d) called\n", i);
u.sum = segtree[lson(i)].sum + segtree[rson(i)].sum;
u.sum %= MOD;
debug("segtree[%d].sum is now %lld\n", i, segtree[i].sum);
}
void pushdown(int i)
{
debug("pushdown(%d) called\n", i);
debug("");
ls.lazy_add *= u.lazy_times; ls.lazy_add %= MOD;
ls.lazy_add += u.lazy_add; ls.lazy_add %= MOD;
ls.lazy_times *= u.lazy_times; ls.lazy_times %= MOD;
ls.sum = ls.sum * u.lazy_times + (ls.r - ls.l) * u.lazy_add; ls.sum %= MOD;
rs.lazy_add *= u.lazy_times; rs.lazy_add %= MOD;
rs.lazy_add += u.lazy_add; rs.lazy_add %= MOD;
rs.lazy_times *= u.lazy_times; rs.lazy_times %= MOD;
rs.sum = rs.sum * u.lazy_times + (rs.r - rs.l) * segtree[i].lazy_add; rs.sum %= MOD;
u.lazy_add = 0;
u.lazy_times = 1;
/*debug("segtree[%d].lazy is now %lld\n", lson(i), segtree[lson(i)].lazy);
debug("segtree[%d].sum is now %lld\n", lson(i), segtree[lson(i)].sum);
debug("segtree[%d].lazy is now %lld\n", rson(i), segtree[rson(i)].lazy);
debug("segtree[%d].sum is now %lld\n", rson(i), segtree[rson(i)].sum);
debug("segtree[%d].lazy is now 0\n", i);*/
}
void build(int l, int r, int i)
{
u.l = l, u.r = r;
u.lazy_times = 1;
if (r - l == 1)
{
u.sum = a[l];
debug("segtree[%d].sum is now %lld\n", i, a[l]);
return;
}
int mid = (l + r) >> 1;
build(l, mid, lson(i));
build(mid, r, rson(i));
pushup(i);
}
ll query(int l, int r, int i)
{
debug("query(%d, %d, %d) called\n", l, r, i);
pushdown(i);
int left = u.l, right = u.r;
int mid = (left + right) >> 1;
ll ret;
if (l == left && r == right)
ret = u.sum;
else if (l >= left && r <= mid)
ret = query(l, r, lson(i));
else if (l >= mid && r <= right)
ret = query(l, r, rson(i));
else
ret = query(l, mid, lson(i)) + query(mid, r, rson(i)), ret %= MOD;
debug("query(%d, %d, %d) returned %lld\n", l, r, i, ret);
return ret;
}
/*
void modify_point(int p, int i, int delta)
{
debug("modify(%d, %d, %d) called\n", p, i, delta);
if (segtree[i].r - segtree[i].l == 1)
{
segtree[i].sum += delta;
return;
}
int mid = (segtree[i].l + segtree[i].r) >> 1;
if (p < mid)
modify(p, lson(i), delta);
else
modify(p, rson(i), delta);
pushup(i);
}
*/
void modify_add(int l, int r, int i, int delta)
{
debug("modify(%d, %d, %d) called\n", l, r, i);
int left = u.l, right = u.r;
int mid = (left + right) >> 1;
if (l == left && r == right)
u.lazy_add += delta, u.sum += delta * (u.r - u.l),
segtree[i].lazy_add %= MOD, segtree[i].sum %= MOD;
//debug("segtree[%d].lazy is now %lld\nsegtree[%d].sum is now %lld\n", i, segtree[i].lazy_add, i, segtree[i].sum);
else
{
pushdown(i);
if (l >= left && r <= mid)
modify_add(l, r, lson(i), delta);
else if (l >= mid && r <= right)
modify_add(l, r, rson(i), delta);
else
modify_add(l, mid, lson(i), delta), modify_add(mid, r, rson(i), delta);
pushup(i);
}
}
void modify_times(int l, int r, int i, int delta)
{
debug("modify(%d, %d, %d) called\n", l, r, i);
int left = u.l, right = u.r;
int mid = (left + right) >> 1;
if (l == left && r == right)
u.lazy_times *= delta, u.sum *= delta;
//debug("segtree[%d].lazy is now %lld\nsegtree[%d].sum is now %lld\n", i, segtree[i].lazy_add, i, segtree[i].sum);
else
{
pushdown(i);
if (l >= left && r <= mid)
modify_times(l, r, lson(i), delta);
else if (l >= mid && r <= right)
modify_times(l, r, rson(i), delta);
else
modify_times(l, mid, lson(i), delta), modify_times(mid, r, rson(i), delta);
pushup(i);
}
}
void dump(int i)
{
#ifndef ONLINE_JUDGE
if (u.l == u.r)
return;
debug("segtree[%d]: left = %d, right = %d, sum = %lld, lazy = %lld\n", i, segtree[i].l, segtree[i].r, segtree[i].sum, segtree[i].lazy_add);
dump(lson(i));
dump(rson(i));
#endif
}
int main()
{
int n, q;
scanf("%d %d %d", &n, &q, &MOD);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
build(1, n + 1, 1);
while (q--)
{
int op, x, y, k;
scanf("%d", &op);
if (op == 1)
scanf("%d %d %d", &x, &y, &k), modify_add(x, y + 1, 1, k);
else if (op == 2)
scanf("%d %d %d", &x, &y, &k), modify_times(x, y + 1, 1, k);
else if (op == 3)
scanf("%d %d", &x, &y), printf("%lld\n", query(x, y + 1, 1));
debug("DUMP\n");
dump(1);
}
return 0;
}