#include <bits/stdc++.h>
#define int long long
//#pragma GCC optimize(3, 2, "Ofast")

using namespace std;

const int N = 1000005 * 4;
struct node {int l, r, d, add, mul; } t[N];
int n, m, p, a[N];

void pushdown(int rt) {
	int l = rt * 2, r = l + 1;
	t[l].d = (t[l].d * t[rt].mul + (t[l].r - t[l].l + 1) * t[rt].add) % p;
	t[r].d = (t[r].d * t[rt].mul + (t[r].r - t[r].l + 1) * t[rt].add) % p;
	t[l].mul = t[l].mul * t[rt].mul % p;
	t[r].mul = t[r].mul * t[rt].mul % p;
	t[l].add = (t[l].add * t[rt].mul + t[rt].add) % p;
	t[r].add = (t[r].add * t[rt].mul + t[rt].add) % p;
	t[rt].add = 0;
	t[rt].mul = 1;
}

void build(int rt, int l, int r) {
	t[rt].l = l, t[rt].r = r;
	t[rt].mul = 1;
	if (l == r) {
		t[rt].d = a[l];
		return;
	}
	int mid = l + r >> 1;
	build(rt * 2, l, mid);
	build(rt * 2 + 1, mid + 1, r);
	t[rt].d = (t[rt * 2].d + t[rt * 2 + 1].d) % p;
}

void Add(int rt, int l, int r, int v) {
	if (l <= t[rt].l && t[rt].r <= r) {
		t[rt].d = (t[rt].d + (t[rt].r - t[rt].l + 1) * v) % p;
		t[rt].add = (t[rt].add + v) % p;
		return;
	}
	pushdown(rt);
	int mid = t[rt].l + t[rt].r >> 1;
	if (l <= mid) Add(rt * 2, l, r, v);
	if (r > mid) Add(rt * 2 + 1, l, r, v);
	t[rt].d = (t[rt * 2].d + t[rt * 2 + 1].d);
}

void Mul(int rt, int l, int r, int v) {
	if (l <= t[rt].l && t[rt].r <= r) {
		t[rt].d = t[rt].d * v % p;
		t[rt].add = t[rt].add * v % p;
		t[rt].mul = t[rt].mul * v % p;
		return;
	}
	pushdown(rt);
	int mid = t[rt].l + t[rt].r >> 1;
	if (l <= mid) Mul(rt * 2, l, r, v);
	if (r > mid) Mul(rt * 2 + 1, l, r, v);
	t[rt].d = (t[rt * 2].d + t[rt * 2 + 1].d) % p;
}

int query(int rt, int l, int r) {
	if (l <= t[rt].l && t[rt].r <= r) {
		return t[rt].d;
	}
	pushdown(rt);
	int mid = t[rt].l + t[rt].r >> 1;
	int ans = 0;
	if (l <= mid) ans += query(rt * 2, l, r);
	if (r > mid) ans += query(rt * 2 + 1, l, r);
	return ans % p;
}

signed 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];
	cin >> m;
	build(1, 1, n);
	while (m--) {
		int cmd, x, y, z; cin >> cmd >> x >> y;
		if (cmd == 3) {
			cout << query(1, x, y) % p << "\n";
		}
		else {
			cin >> z;
			if (cmd == 1) {
				Mul(1, x, y, z);
			}
			else {
				Add(1, x, y, z);
			}
		}
	}

	return 0;
}