#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+5;
typedef long long ll;
int lf[N], rt[N], cnt=1, n, m, a[N], p;
ll t[N], add[N], mul[N];
void build(int x, int l, int r){
	if(l == r){
		t[x] = a[l], add[x] = 0, mul[x] = 1;
		return;
	}
	int mid = (l + r) / 2;
	lf[x] = ++cnt, build(lf[x], l, mid), rt[x] = ++cnt, build(rt[x], mid+1, r);
	t[x] = (t[lf[x]] + t[rt[x]]) % p, add[x] = 0, mul[x] = 1;
}
void pushdown(int x, int l, int r){
	if(add[x] == 0 && mul[x] == 1) return;
	int mid = (l + r) / 2;
	t[lf[x]] = (t[lf[x]] * mul[x] + add[x]) % p, (mul[lf[x]] *= mul[x]) %= p, (add[lf[x]] = add[lf[x]] * mul[x] % p + add[x]) %= p;
	t[rt[x]] = (t[rt[x]] * mul[x] + add[x]) % p, (mul[rt[x]] *= mul[x]) %= p, (add[rt[x]] = add[rt[x]] * mul[x] % p + add[x]) %= p;
	add[x] = 0, mul[x] = 1;
}
void modify(int x, int l, int r, int a, int b, ll d){
	if(a <= l && r <= b){
		(add[x] += d) %= p, (t[x] += d * (r-l+1) % p) %= p;
		return;
	}
	pushdown(x, l, r);
	int mid = (l + r) / 2;
	if(a <= mid) modify(lf[x], l, mid, a, b, d);
	if(b > mid) modify(rt[x], mid+1, r, a, b, d);
	t[x] = (t[lf[x]] + t[rt[x]]) % p;
}
void qmul(int x, int l, int r, int a, int b, ll d){
	if(a <= l && r <= b){
		(t[x] *= d) %= p, (add[x] *= d) %= p, (mul[x] *= d) %= p;
		return;
	}
	pushdown(x, l, r);
	int mid = (l + r) / 2;
	if(a <= mid) modify(lf[x], l, mid, a, b, d);
	if(b > mid) modify(rt[x], mid+1, r, a, b, d);
	t[x] = (t[lf[x]] + t[rt[x]]) % p;
}
ll query(int x, int l, int r, int a, int b){
	if(a <= l && r <= b) return t[x]%p;
	int mid = (l + r) / 2;
	ll s = 0;
	pushdown(x, l, r);
	if(a <= mid) s += query(lf[x], l, mid, a, b);
	if(b > mid) s += query(rt[x], mid+1, r, a, b);
	return s%p;
}
int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n>>p;
	for(int i = 1; i <= n; i++) cin>>a[i];
	build(1, 1, n);
	cin>>m;
	while(m--){
		int c, x, y, z;
		cin>>c>>x>>y;
		if(c == 3){
			cout<<query(1, 1, n, x, y)<<"\n";
			
		}
		else if(c == 2){
			cin>>z;
			modify(1, 1, n, x, y, z);
		}
		else{
			cin>>z;
			qmul(1, 1, n, x, y, z);
		}
	}
	return 0;
}