// LUOGU_RID: 131528874
#include <bits/stdc++.h>
#define ll long long
#define lson u << 1
#define rson u << 1 | 1
#define mid (L[u] + R[u] >> 1)
using namespace std;

const int N = 1e5 + 10;
int L[N << 2], R[N << 2], sum[N << 2], val[N << 2], mul[N << 2], c[N << 2][12];
int k, p[N], phi, tmp;
int n, mod, a[N];
int m, op, x, y, z;

inline int pwr(int b, int k) {
	int res = 1;
	while (k) {
		if (k & 1) res = (ll)res * b % mod;
		b = (ll)b * b % mod; k >>= 1;
	}
	return res;
}

inline void pushup(int u) {
	sum[u] = (sum[lson] + sum[rson]) % mod;
}

inline void apply(int u, int v) {
	sum[u] = (ll)sum[u] * v % mod;
	mul[u] = (ll)mul[u] * v % mod;
}

inline void pushdown(int u) {
	apply(lson, mul[u]);
	apply(rson, mul[u]);
	val[lson] = (ll)val[lson] * val[u] % mod;
	val[rson] = (ll)val[rson] * val[u] % mod;
	mul[u] = val[u] = 1;
	for (int i = 1; i <= k; i++) {
		c[lson][i] += c[u][i];
		c[rson][i] += c[u][i];
		c[u][i] = 0;
	}
}

inline void build(int u, int l, int r) {
	L[u] = l, R[u] = r;
	mul[u] = val[u] = 1;
	if (l == r) {
		sum[u] = a[l] % mod;
		for (int i = 1; i <= k; i++) while (a[l] % p[i] == 0) c[u][i]++, a[l] /= p[i];
		val[u] = a[l] % mod;
		return;
	}
	build(lson, l, mid);
	build(rson, mid + 1, r);
	pushup(u);
}

inline void modify(int u, int l, int r, int x) {
	if (l <= L[u] && R[u] <= r) {
		apply(u, x);
		for (int i = 1; i <= k; i++) while (x % p[i] == 0) c[u][i]++, x /= p[i];
		val[u] = (ll)val[u] * x % mod;
		return;
	}
	pushdown(u);
	if (l <= mid) modify(lson, l, r, x);
	if (r > mid) modify(rson, l, r, x);
	pushup(u);
}

inline void divide(int u, int x, int v) {
	if (L[u] == R[u]) {
		for (int i = 1; i <= k; i++) while (v % p[i] == 0) c[u][i]--, v /= p[i];
		val[u] = (ll)val[u] * pwr(v, phi - 1) % mod;
		sum[u] = val[u];
		for (int i = 1; i <= k; i++) sum[u] = (ll)sum[u] * pwr(p[i], c[u][i]) % mod;
		return;
	}
	pushdown(u);
	if (x <= mid) divide(lson, x, v);
	else divide(rson, x, v);
	pushup(u);
}

inline int query(int u, int l, int r) {
	if (l <= L[u] && R[u] <= r) return sum[u];
	pushdown(u);
	int res = 0;
	if (l <= mid) res = (res + query(lson, l, r)) % mod;
	if (r > mid) res = (res + query(rson, l, r)) % mod;
	return res;
}

inline void init() {
	phi = tmp = mod;
	for (int i = 2; i * i <= tmp; i++) {
		if (tmp % i) continue;
		p[++k] = i;
		phi = phi / i * (i - 1);
		while (tmp % i == 0) tmp /= i;
	}
	if (tmp > 1) p[++k] = tmp, phi = phi / tmp * (tmp - 1);
}

int main() {
	scanf("%d%d", &n, &mod);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	init();
	build(1, 1, n);
	scanf("%d", &m);
	while (m--) {
		scanf("%d%d%d", &op, &x, &y);
		if (op == 1) scanf("%d", &z), modify(1, x, y, z);
		if (op == 2) divide(1, x, y);
		if (op == 3) printf("%d\n", query(1, x, y));
	}
	return 0;
}