rt, 0pts求条

#include <bits/stdc++.h>
using namespace std;
#define Max 100005
#define left(x) 2*x
#define right(x) 2*x+1
#define int long long
#define rep(i, a, b) for(int i = a;i <= b;i++)
#define len(l, r) r-l+1
struct node{
	int lc, rc, add = 0, mul = 1, sum;
}tree[2*Max];
int a[Max], n, m, mod;
void pushup(int p)
{
	tree[p].sum = (tree[left(p)].sum+tree[right(p)].sum)%mod;
}
void pushdown(int p)
{
	tree[left(p)].mul = tree[p].mul*tree[left(p)].mul%mod;
	tree[right(p)].mul = tree[p].mul*tree[right(p)].mul%mod;
	
	tree[left(p)].add = (tree[left(p)].add*tree[p].mul%mod+tree[p].add)%mod;
	tree[right(p)].add = (tree[right(p)].add*tree[p].mul%mod+tree[p].add)%mod;
	
	tree[left(p)].sum = (tree[p].mul*tree[left(p)].sum%mod+tree[p].add*len(tree[left(p)].lc, tree[left(p)].rc)%mod)%mod;
	tree[right(p)].sum = (tree[p].mul*tree[right(p)].sum%mod+tree[p].add*len(tree[right(p)].lc, tree[right(p)].rc)%mod)%mod;
	
	tree[p].add = 0;tree[p].mul = 1;
}
void build(int p, int l, int r)
{
	tree[p].lc = l;
	tree[p].rc = r;
	if(l == r)
	{
		tree[p].sum = a[l];
		return ;
	}
	int mid = l+r >> 1;
	build(left(p), l, mid);
	build(right(p), mid+1, r);
	pushup(p);
}
void addition(int p, int l, int r, int x, int y, int val)
{
	if(x <= l&&y >= r)
	{
		tree[p].sum = (tree[p].sum+val*len(l, r))%mod;
		tree[p].add = (tree[p].add+val)%mod;
		return ;
	}
	int mid = l+r >> 1;
	pushdown(p);
	if(x <= mid)addition(left(p), l, mid, x, y, val);
	if(y > mid)addition(right(p), mid+1, r, x, y, val);
	pushup(p);
}
void multiply(int p, int l, int r, int x, int y, int val)
{
	if(x <= l&&y >= r)
	{
		tree[p].sum = tree[p].sum*val%mod;
		tree[p].mul = tree[p].mul*val%mod;
		tree[p].add = tree[p].add*val%mod;
		return ;
	}
	int mid = l+r >> 1;
	pushdown(p);
	if(x <= mid)multiply(left(p), l, mid, x, y, val);
	if(y > mid)multiply(right(p), mid+1, r, x, y, val);
	pushup(p);
}
int query(int p, int l, int r, int x, int y)
{
	int mid = l+r >> 1;
	if(x <= l&&y >= r)return tree[p].sum%mod;
	pushdown(p);
	int cnt = 0;
	if(x <= mid)cnt += query(left(p), l, mid, x, y);
	if(y > mid)cnt += query(right(p), mid+1, r, x, y);
	return cnt%mod;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n >> mod;
	rep(i, 1, n)cin >> a[i], a[i] %= mod;
	build(1, 1, n);
	cin >> m;
	rep(i, 1, m)
	{
		int op, x, y, val;
		cin >> op;
		if(op == 1)cin >> x >> y >> val, multiply(1, 1, n, x, y, val);
		if(op == 2)cin >> x >> y >> val, addition(1, 1, n, x, y, val);
		if(op == 3)cin >> x >> y, cout << query(1, 1, n, x, y) << endl;
	}
	return 0;
}