#include <bits/stdc++.h>

#define LL long long

#define ls(x) (x << 1)

#define rs(x) ((x << 1) | 1)

using namespace std;

const int maxn = 100010;

int m;

int p[20], b[maxn], tot, re[10];

LL Phi;

LL qpow(LL a, LL b) {

	LL ans = 1;

	for (; b; b >>= 1) {

		if(b & 1) ans = (ans * a) % m;

		a = a * a % m;

	}

	return ans;

}

LL phi(LL n) {

	LL ans = n;

	for (int i = 2; i * i <= n; i++) {

		if(n % i == 0) {

			ans = ans / i * (i - 1);

			p[tot++] = i;

			while(n % i == 0) n /= i;

		}

	}

	if(n > 1) {

		p[tot++] = n;

		ans = ans / n * (n - 1);

	}

	return ans;

}

struct SegmentTree {

	LL remain, rtag;

	LL tag, sum;

	LL a[10], flag[10];

};

SegmentTree tr[maxn * 4];

void pushup(int o) {

	tr[o].sum = (tr[ls(o)].sum + tr[rs(o)].sum) % m;

}

void pushdown(int o) {

	if(tr[o].rtag != 1) {

		tr[ls(o)].remain = (tr[ls(o)].remain * tr[o].rtag) % m;

		tr[ls(o)].rtag = (tr[ls(o)].rtag * tr[o].rtag) % m;

		tr[rs(o)].remain = (tr[rs(o)].remain * tr[o].rtag) % m;

		tr[rs(o)].rtag = (tr[rs(o)].rtag * tr[o].rtag) % m;

		tr[o].rtag = 1;

	}

	if(tr[o].tag != 1) {

		tr[ls(o)].sum = (tr[ls(o)].sum * tr[o].tag) % m;

		tr[ls(o)].tag = (tr[ls(o)].tag * tr[o].tag) % m;

		tr[rs(o)].sum = (tr[rs(o)].sum * tr[o].tag) % m;

		tr[rs(o)].tag = (tr[rs(o)].tag * tr[o].tag) % m;

		tr[o].tag = 1;

	}

	for (int i = 0; i < tot; i++) {

		tr[ls(o)].a[i] = (tr[ls(o)].a[i] + tr[o].flag[i]);

		tr[ls(o)].flag[i] = (tr[ls(o)].flag[i] + tr[o].flag[i]);

		tr[rs(o)].a[i] = (tr[rs(o)].a[i] + tr[o].flag[i]);

		tr[rs(o)].flag[i] = (tr[rs(o)].flag[i] + tr[o].flag[i]);

		tr[o].flag[i] = 0;

	}

}

void build(int o, int l, int r) {

	tr[o].remain = tr[o].tag = tr[o].sum = tr[o].rtag = 1;

	memset(tr[o].a, 0, sizeof(tr[o].a));

	memset(tr[o].flag, 0, sizeof(tr[o].flag));

	if(l == r) {

		tr[o].sum = b[l] % m;

		for (int i = 0; i < tot; i++) {

			while(b[l] % p[i] == 0) {

				b[l] /= p[i];

				tr[o].a[i]++;

			}

		}

		tr[o].remain = b[l] % m;

		return;

	}

	int mid = (l + r) >> 1;

	build(ls(o), l, mid);

	build(rs(o), mid + 1, r);

	pushup(o);

}

void mul(int o, int l, int r, int ql, int qr, LL x, LL y) {

	if(l >= ql && r <= qr) {

		tr[o].sum = (tr[o].sum * x) % m;

		tr[o].tag = (tr[o].tag * x) % m;

		tr[o].remain = (tr[o].remain * y) % m;

		tr[o].rtag = (tr[o].rtag * y) % m;

		for (int i = 0; i < tot; i++) {

			tr[o].flag[i] += re[i];

			tr[o].a[i] += re[i];

		}

		return;

	}

	pushdown(o);

	int mid = (l + r) >> 1;

	if(ql <= mid) mul(ls(o), l, mid, ql, qr, x, y);

	if(qr > mid) mul(rs(o), mid + 1, r, ql, qr, x, y);

	pushup(o);

}

void div(int o, int l, int r, int pos, LL y) {

	if(l == r) {

		for (int i = 0; i < tot; i++) {

			while(y % p[i] == 0) y /= p[i], tr[o].a[i]--;

		}

		tr[o].remain = (tr[o].remain * qpow(y, Phi - 1)) % m;

		tr[o].sum = tr[o].remain;

		for (int i = 0; i < tot; i++)

			tr[o].sum = (tr[o].sum * qpow(p[i], tr[o].a[i])) % m;

		return;

	}

	pushdown(o);

	int mid = (l + r) >> 1;

	if(pos <= mid) div(ls(o), l, mid, pos, y);

	else div(rs(o), mid + 1, r, pos, y);

	pushup(o);

}

LL query(int o, int l, int r, int ql, int qr) {

	if(l >= ql && r <= qr) return tr[o].sum;

	pushdown(o);

	int mid = (l + r) >> 1;

	LL ans = 0;

	if(ql <= mid) ans = (ans + query(ls(o), l, mid, ql, qr)) % m;

	if(qr > mid) ans = (ans + query(rs(o), mid + 1, r, ql, qr)) % m;

	return ans;

}

int main() {

	int n;

	scanf("%d%lld", &n, &m);

	Phi = phi(m);

	for (int i = 1; i <= n; i++) {

		scanf("%d", &b[i]);

	}

	int t, op, x, y, z;

	build(1, 1, n);

	scanf("%d", &t);

	while(t--) {

		scanf("%d", &op);

		if(op == 1) {

			scanf("%d%d%d", &x, &y, &z);

			int tmp = z;

			for (int i = 0; i < tot; i++) {

				re[i] = 0;

				while(tmp % p[i] == 0) {

					tmp /= p[i];

					re[i]++;

				}

			}

			mul(1, 1, n, x, y, z, tmp);

		} else if(op == 2) {

			scanf("%d%d", &x, &y);

			div(1, 1, n, x, y);

		} else {

			scanf("%d%d", &x, &y);

			printf("%lld\n", query(1, 1, n, x, y));

		}

	}

}