#include <bits/stdc++.h>
using namespace std;
int phi(int n) {
int res = n;
for (int i = 2; i*i <= n; ++i)
if (n % i == 0) {
while (n % i == 0)
n /= i;
res -= res / i;
}
if (n > 1)
res -= res / n;
return res;
}
vector <int> factorize(int x) {
vector <int> res;
for (int i = 2; i*i <= x; ++i) {
if (x%i == 0) {
res.push_back(i);
}
while (x%i == 0) {
x /= i;
}
}
if (x > 1) res.push_back(x);
return res;
}
#define fmod i_love_pelmeny
int mod;
vector <int> fmod;
const int N = (int)2e5+10;
vector <pair <int, int> > f[N];
vector <int> pw[25];
//vector <int> realpw[25];
int goodpart[N];
int inv[N];
int n, a[N];
int id[N];
int binpow(int a, int b) {
int res = 1;
while (b > 0) {
if (b&1) res = 1ll*res*a%mod;
b >>= 1;
a = 1ll*a*a%mod;
}
return res;
}
struct node {
vector <int> degrees;
int tl, tr;
int sum, here;
bool flag = false;
node *le, *ri;
int calc_real_sum() {
// if (!flag) return sum;
int res = here;
for (int i = 0; i < degrees.size(); ++i) {
res = 1ll*res*pw[i][degrees[i]]%mod;
}
return res;
}
void push_down() {
if (!flag) return;
int i = 0;
for (auto & x : degrees) {
le->degrees[i] += x;
ri->degrees[i] += x;
le->sum = 1ll*le->sum*pw[i][x]%mod;
ri->sum = 1ll*ri->sum*pw[i][x]%mod;
x = 0;
++i;
}
le->here = 1ll*le->here*here%mod;
le->sum = 1ll*le->sum*here%mod;
ri->here = 1ll*ri->here*here%mod;
ri->sum = 1ll*ri->sum*here%mod;
here = 1;
flag = false;
le->flag = ri->flag = true;
}
void combine() {
sum = (le->sum+ri->sum)%mod;
}
void multiply(int l, int r, int x) {
if (r < tl || tr < l) return;
if (l <= tl && tr <= r) {
flag = true;
for (auto p : f[x]) {
degrees[id[p.first]-1] += p.second;
}
here = 1ll*here*goodpart[x]%mod;
sum = 1ll*sum*x%mod;
return;
}
push_down();
le->multiply(l, r, x);
ri->multiply(l, r, x);
combine();
}
void divide(int pos, int x) {
if (tl == tr) {
for (auto p : f[x]) {
degrees[id[p.first]-1] -= p.second;
}
here = 1ll*here*inv[goodpart[x]]%mod;
sum = calc_real_sum();
return;
}
push_down();
if (pos <= (tl+tr)/2) {
le->divide(pos, x);
} else {
ri->divide(pos, x);
}
combine();
}
int get(int l, int r) {
if (r < tl || tr < l) {
return 0;
}
if (l <= tl && tr <= r) {
return sum;
}
push_down();
return (le->get(l, r)+ri->get(l, r))%mod;
}
node(int l, int r, int dsize) {
tl = l;
tr = r;
sum = 1;
here = 1;
degrees.resize(dsize);
if (l == r) {
multiply(l, r, a[l]);
return;
}
le = new node(l, (l+r)/2, dsize);
ri = new node((l+r)/2+1, r, dsize);
combine();
}
};
struct query {
int x, l, r, t;
query() {}
};
node *t;
vector <query> q;
void precalc_base() {
fmod = factorize(mod);
if (fmod.back() >= N) fmod.pop_back();
vector <int> deg(N);
for (int i = 0; i < fmod.size(); ++i) {
id[fmod[i]] = i+1;
for (int j = fmod[i]; j < N; j += fmod[i]) {
if ((j/fmod[i])%fmod[i]) {
deg[j] = 1;
} else {
deg[j] = deg[j/fmod[i]]+1;
}
f[j].emplace_back(fmod[i], deg[j]);
}
}
for (int i = 1; i < N; ++i) {
goodpart[i] = i;
goodpart[i] = goodpart[i/__gcd(i, mod)];
}
}
void precalc_inverse() {
vector <int> mn(N);
for (int i = 2; i < N; ++i) {
if (mn[i]) continue;
for (int j = i+i; j < N; j += i) {
if (!mn[j]) mn[j] = i;
}
}
int mod_phi = phi(mod);
inv[1] = 1;
for (int i = 2; i < N; ++i) {
if (!mn[i]) inv[i] = binpow(i, mod_phi-1);
else inv[i] = 1ll*inv[i/mn[i]]*inv[mn[i]]%mod;
}
}
void precalc_powers() {
vector <int> max_entry(fmod.size());
for (int i = 1; i <= n; ++i) {
for (auto p : f[a[i]]) {
max_entry[id[p.first]-1] += p.second;
}
}
for (const auto& w : q) {
if (w.t != 1) continue;
for (auto p : f[w.x]) {
max_entry[id[p.first]-1] += p.second;
}
}
for (int i = 0; i < fmod.size(); ++i) {
pw[i].resize(max_entry[i]+1);
pw[i][0] = 1;
for (int j = 1; j < pw[i].size(); ++j) {
pw[i][j] = 1ll*pw[i][j-1]*fmod[i]%mod;
}
}
}
void precalc() {
precalc_base();
precalc_inverse();
precalc_powers();
t = new node(1, n, fmod.size());
cerr << 1.0*clock()/CLOCKS_PER_SEC << endl;
}
int main() {
// ios_base::sync_with_stdio(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // LOCAL
scanf("%d%d", &n, &mod);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
int m; scanf("%d", &m);
q.resize(m);
for (int i = 0; i < m; ++i) {
scanf("%d", &q[i].t);
scanf("%d", &q[i].l);
if (q[i].t != 2)
scanf("%d", &q[i].r);
if (q[i].t != 3)
scanf("%d", &q[i].x);
}
precalc();
for (const auto& p : q) {
if (p.t == 1) {
t->multiply(p.l, p.r, p.x);
}
if (p.t == 2) {
t->divide(p.l, p.x);
}
if (p.t == 3) {
printf("%d\n", t->get(p.l, p.r));
}
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgcGhpKGludCBuKSB7CglpbnQgcmVzID0gbjsKCWZvciAoaW50IGkgPSAyOyBpKmkgPD0gbjsgKytpKQoJCWlmIChuICUgaSA9PSAwKSB7CgkJCXdoaWxlIChuICUgaSA9PSAwKQoJCQkJbiAvPSBpOwoJCQlyZXMgLT0gcmVzIC8gaTsKCQl9CglpZiAobiA+IDEpCgkJcmVzIC09IHJlcyAvIG47CglyZXR1cm4gcmVzOwp9Cgp2ZWN0b3IgPGludD4gZmFjdG9yaXplKGludCB4KSB7CiAgICB2ZWN0b3IgPGludD4gcmVzOwogICAgZm9yIChpbnQgaSA9IDI7IGkqaSA8PSB4OyArK2kpIHsKICAgICAgICBpZiAoeCVpID09IDApIHsKICAgICAgICAgICAgcmVzLnB1c2hfYmFjayhpKTsKICAgICAgICB9CiAgICAgICAgd2hpbGUgKHglaSA9PSAwKSB7CiAgICAgICAgICAgIHggLz0gaTsKICAgICAgICB9CiAgICB9CiAgICBpZiAoeCA+IDEpIHJlcy5wdXNoX2JhY2soeCk7CiAgICByZXR1cm4gcmVzOwp9CgojZGVmaW5lIGZtb2QgaV9sb3ZlX3BlbG1lbnkKCmludCBtb2Q7CnZlY3RvciA8aW50PiBmbW9kOwpjb25zdCBpbnQgTiA9IChpbnQpMmU1KzEwOwp2ZWN0b3IgPHBhaXIgPGludCwgaW50PiA+IGZbTl07CnZlY3RvciA8aW50PiBwd1syNV07Ci8vdmVjdG9yIDxpbnQ+IHJlYWxwd1syNV07CmludCBnb29kcGFydFtOXTsKaW50IGludltOXTsKaW50IG4sIGFbTl07CmludCBpZFtOXTsKCmludCBiaW5wb3coaW50IGEsIGludCBiKSB7CiAgICBpbnQgcmVzID0gMTsKICAgIHdoaWxlIChiID4gMCkgewogICAgICAgIGlmIChiJjEpIHJlcyA9IDFsbCpyZXMqYSVtb2Q7CiAgICAgICAgYiA+Pj0gMTsKICAgICAgICBhID0gMWxsKmEqYSVtb2Q7CiAgICB9CiAgICByZXR1cm4gcmVzOwp9CgpzdHJ1Y3Qgbm9kZSB7CiAgICB2ZWN0b3IgPGludD4gZGVncmVlczsKICAgIGludCB0bCwgdHI7CiAgICBpbnQgc3VtLCBoZXJlOwogICAgYm9vbCBmbGFnID0gZmFsc2U7CiAgICBub2RlICpsZSwgKnJpOwoKICAgIGludCBjYWxjX3JlYWxfc3VtKCkgewovLyAgICAgICAgaWYgKCFmbGFnKSByZXR1cm4gc3VtOwogICAgICAgIGludCByZXMgPSBoZXJlOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgZGVncmVlcy5zaXplKCk7ICsraSkgewogICAgICAgICAgICByZXMgPSAxbGwqcmVzKnB3W2ldW2RlZ3JlZXNbaV1dJW1vZDsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIHJlczsKICAgIH0KICAgIHZvaWQgcHVzaF9kb3duKCkgewogICAgICAgIGlmICghZmxhZykgcmV0dXJuOwogICAgICAgIGludCBpID0gMDsKICAgICAgICBmb3IgKGF1dG8gJiB4IDogZGVncmVlcykgewogICAgICAgICAgICBsZS0+ZGVncmVlc1tpXSArPSB4OwogICAgICAgICAgICByaS0+ZGVncmVlc1tpXSArPSB4OwoKICAgICAgICAgICAgbGUtPnN1bSA9IDFsbCpsZS0+c3VtKnB3W2ldW3hdJW1vZDsKICAgICAgICAgICAgcmktPnN1bSA9IDFsbCpyaS0+c3VtKnB3W2ldW3hdJW1vZDsKCiAgICAgICAgICAgIHggPSAwOwogICAgICAgICAgICArK2k7CiAgICAgICAgfQogICAgICAgIGxlLT5oZXJlID0gMWxsKmxlLT5oZXJlKmhlcmUlbW9kOwogICAgICAgIGxlLT5zdW0gPSAxbGwqbGUtPnN1bSpoZXJlJW1vZDsKICAgICAgICByaS0+aGVyZSA9IDFsbCpyaS0+aGVyZSpoZXJlJW1vZDsKICAgICAgICByaS0+c3VtID0gMWxsKnJpLT5zdW0qaGVyZSVtb2Q7CiAgICAgICAgaGVyZSA9IDE7CiAgICAgICAgZmxhZyA9IGZhbHNlOwogICAgICAgIGxlLT5mbGFnID0gcmktPmZsYWcgPSB0cnVlOwogICAgfQogICAgdm9pZCBjb21iaW5lKCkgewogICAgICAgIHN1bSA9IChsZS0+c3VtK3JpLT5zdW0pJW1vZDsKICAgIH0KCiAgICB2b2lkIG11bHRpcGx5KGludCBsLCBpbnQgciwgaW50IHgpIHsKICAgICAgICBpZiAociA8IHRsIHx8IHRyIDwgbCkgcmV0dXJuOwogICAgICAgIGlmIChsIDw9IHRsICYmIHRyIDw9IHIpIHsKICAgICAgICAgICAgZmxhZyA9IHRydWU7CiAgICAgICAgICAgIGZvciAoYXV0byBwIDogZlt4XSkgewogICAgICAgICAgICAgICAgZGVncmVlc1tpZFtwLmZpcnN0XS0xXSArPSBwLnNlY29uZDsKICAgICAgICAgICAgfQogICAgICAgICAgICBoZXJlID0gMWxsKmhlcmUqZ29vZHBhcnRbeF0lbW9kOwogICAgICAgICAgICBzdW0gPSAxbGwqc3VtKnglbW9kOwogICAgICAgICAgICByZXR1cm47CiAgICAgICAgfQogICAgICAgIHB1c2hfZG93bigpOwogICAgICAgIGxlLT5tdWx0aXBseShsLCByLCB4KTsKICAgICAgICByaS0+bXVsdGlwbHkobCwgciwgeCk7CiAgICAgICAgY29tYmluZSgpOwogICAgfQogICAgdm9pZCBkaXZpZGUoaW50IHBvcywgaW50IHgpIHsKICAgICAgICBpZiAodGwgPT0gdHIpIHsKICAgICAgICAgICAgZm9yIChhdXRvIHAgOiBmW3hdKSB7CiAgICAgICAgICAgICAgICBkZWdyZWVzW2lkW3AuZmlyc3RdLTFdIC09IHAuc2Vjb25kOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGhlcmUgPSAxbGwqaGVyZSppbnZbZ29vZHBhcnRbeF1dJW1vZDsKICAgICAgICAgICAgc3VtID0gY2FsY19yZWFsX3N1bSgpOwogICAgICAgICAgICByZXR1cm47CiAgICAgICAgfQogICAgICAgIHB1c2hfZG93bigpOwogICAgICAgIGlmIChwb3MgPD0gKHRsK3RyKS8yKSB7CiAgICAgICAgICAgIGxlLT5kaXZpZGUocG9zLCB4KTsKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICByaS0+ZGl2aWRlKHBvcywgeCk7CiAgICAgICAgfQogICAgICAgIGNvbWJpbmUoKTsKICAgIH0KICAgIGludCBnZXQoaW50IGwsIGludCByKSB7CiAgICAgICAgaWYgKHIgPCB0bCB8fCB0ciA8IGwpIHsKICAgICAgICAgICAgcmV0dXJuIDA7CiAgICAgICAgfQogICAgICAgIGlmIChsIDw9IHRsICYmIHRyIDw9IHIpIHsKICAgICAgICAgICAgcmV0dXJuIHN1bTsKICAgICAgICB9CiAgICAgICAgcHVzaF9kb3duKCk7CiAgICAgICAgcmV0dXJuIChsZS0+Z2V0KGwsIHIpK3JpLT5nZXQobCwgcikpJW1vZDsKICAgIH0KICAgIG5vZGUoaW50IGwsIGludCByLCBpbnQgZHNpemUpIHsKICAgICAgICB0bCA9IGw7CiAgICAgICAgdHIgPSByOwogICAgICAgIHN1bSA9IDE7CiAgICAgICAgaGVyZSA9IDE7CiAgICAgICAgZGVncmVlcy5yZXNpemUoZHNpemUpOwogICAgICAgIGlmIChsID09IHIpIHsKICAgICAgICAgICAgbXVsdGlwbHkobCwgciwgYVtsXSk7CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CiAgICAgICAgbGUgPSBuZXcgbm9kZShsLCAobCtyKS8yLCBkc2l6ZSk7CiAgICAgICAgcmkgPSBuZXcgbm9kZSgobCtyKS8yKzEsIHIsIGRzaXplKTsKICAgICAgICBjb21iaW5lKCk7CiAgICB9Cn07CgpzdHJ1Y3QgcXVlcnkgewogICAgaW50IHgsIGwsIHIsIHQ7CiAgICBxdWVyeSgpIHt9Cn07Cgpub2RlICp0Owp2ZWN0b3IgPHF1ZXJ5PiBxOwoKdm9pZCBwcmVjYWxjX2Jhc2UoKSB7CiAgICBmbW9kID0gZmFjdG9yaXplKG1vZCk7CiAgICBpZiAoZm1vZC5iYWNrKCkgPj0gTikgZm1vZC5wb3BfYmFjaygpOwogICAgdmVjdG9yIDxpbnQ+IGRlZyhOKTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgZm1vZC5zaXplKCk7ICsraSkgewogICAgICAgIGlkW2Ztb2RbaV1dID0gaSsxOwogICAgICAgIGZvciAoaW50IGogPSBmbW9kW2ldOyBqIDwgTjsgaiArPSBmbW9kW2ldKSB7CiAgICAgICAgICAgIGlmICgoai9mbW9kW2ldKSVmbW9kW2ldKSB7CiAgICAgICAgICAgICAgICBkZWdbal0gPSAxOwogICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgZGVnW2pdID0gZGVnW2ovZm1vZFtpXV0rMTsKICAgICAgICAgICAgfQogICAgICAgICAgICBmW2pdLmVtcGxhY2VfYmFjayhmbW9kW2ldLCBkZWdbal0pOwogICAgICAgIH0KICAgIH0KCiAgICBmb3IgKGludCBpID0gMTsgaSA8IE47ICsraSkgewogICAgICAgIGdvb2RwYXJ0W2ldID0gaTsKICAgICAgICBnb29kcGFydFtpXSA9IGdvb2RwYXJ0W2kvX19nY2QoaSwgbW9kKV07CiAgICB9Cn0Kdm9pZCBwcmVjYWxjX2ludmVyc2UoKSB7CiAgICB2ZWN0b3IgPGludD4gbW4oTik7CiAgICBmb3IgKGludCBpID0gMjsgaSA8IE47ICsraSkgewogICAgICAgIGlmIChtbltpXSkgY29udGludWU7CiAgICAgICAgZm9yIChpbnQgaiA9IGkraTsgaiA8IE47IGogKz0gaSkgewogICAgICAgICAgICBpZiAoIW1uW2pdKSBtbltqXSA9IGk7CiAgICAgICAgfQogICAgfQoKICAgIGludCBtb2RfcGhpID0gcGhpKG1vZCk7CiAgICBpbnZbMV0gPSAxOwogICAgZm9yIChpbnQgaSA9IDI7IGkgPCBOOyArK2kpIHsKICAgICAgICBpZiAoIW1uW2ldKSBpbnZbaV0gPSBiaW5wb3coaSwgbW9kX3BoaS0xKTsKICAgICAgICBlbHNlIGludltpXSA9IDFsbCppbnZbaS9tbltpXV0qaW52W21uW2ldXSVtb2Q7CiAgICB9Cn0Kdm9pZCBwcmVjYWxjX3Bvd2VycygpIHsKICAgIHZlY3RvciA8aW50PiBtYXhfZW50cnkoZm1vZC5zaXplKCkpOwogICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgKytpKSB7CiAgICAgICAgZm9yIChhdXRvIHAgOiBmW2FbaV1dKSB7CiAgICAgICAgICAgIG1heF9lbnRyeVtpZFtwLmZpcnN0XS0xXSArPSBwLnNlY29uZDsKICAgICAgICB9CiAgICB9CgogICAgZm9yIChjb25zdCBhdXRvJiB3IDogcSkgewogICAgICAgIGlmICh3LnQgIT0gMSkgY29udGludWU7CiAgICAgICAgZm9yIChhdXRvIHAgOiBmW3cueF0pIHsKICAgICAgICAgICAgbWF4X2VudHJ5W2lkW3AuZmlyc3RdLTFdICs9IHAuc2Vjb25kOwogICAgICAgIH0KICAgIH0KCiAgICBmb3IgKGludCBpID0gMDsgaSA8IGZtb2Quc2l6ZSgpOyArK2kpIHsKICAgICAgICBwd1tpXS5yZXNpemUobWF4X2VudHJ5W2ldKzEpOwogICAgICAgIHB3W2ldWzBdID0gMTsKICAgICAgICBmb3IgKGludCBqID0gMTsgaiA8IHB3W2ldLnNpemUoKTsgKytqKSB7CiAgICAgICAgICAgIHB3W2ldW2pdID0gMWxsKnB3W2ldW2otMV0qZm1vZFtpXSVtb2Q7CiAgICAgICAgfQogICAgfQoKfQp2b2lkIHByZWNhbGMoKSB7CiAgICBwcmVjYWxjX2Jhc2UoKTsKICAgIHByZWNhbGNfaW52ZXJzZSgpOwogICAgcHJlY2FsY19wb3dlcnMoKTsKICAgIHQgPSBuZXcgbm9kZSgxLCBuLCBmbW9kLnNpemUoKSk7CiAgICBjZXJyIDw8IDEuMCpjbG9jaygpL0NMT0NLU19QRVJfU0VDIDw8IGVuZGw7Cn0KCmludCBtYWluKCkgewovLyAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApOwogICAgI2lmZGVmIExPQ0FMCiAgICBmcmVvcGVuKCJpbnB1dC50eHQiLCAiciIsIHN0ZGluKTsKICAgIGZyZW9wZW4oIm91dHB1dC50eHQiLCAidyIsIHN0ZG91dCk7CiAgICAjZW5kaWYgLy8gTE9DQUwKICAgIHNjYW5mKCIlZCVkIiwgJm4sICZtb2QpOwogICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgKytpKSB7CiAgICAgICAgc2NhbmYoIiVkIiwgJmFbaV0pOwogICAgfQogICAgaW50IG07IHNjYW5mKCIlZCIsICZtKTsKICAgIHEucmVzaXplKG0pOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBtOyArK2kpIHsKICAgICAgICBzY2FuZigiJWQiLCAmcVtpXS50KTsKICAgICAgICBzY2FuZigiJWQiLCAmcVtpXS5sKTsKICAgICAgICBpZiAocVtpXS50ICE9IDIpCiAgICAgICAgICAgIHNjYW5mKCIlZCIsICZxW2ldLnIpOwogICAgICAgIGlmIChxW2ldLnQgIT0gMykKICAgICAgICAgICAgc2NhbmYoIiVkIiwgJnFbaV0ueCk7CiAgICB9CiAgICBwcmVjYWxjKCk7CiAgICBmb3IgKGNvbnN0IGF1dG8mIHAgOiBxKSB7CiAgICAgICAgaWYgKHAudCA9PSAxKSB7CiAgICAgICAgICAgIHQtPm11bHRpcGx5KHAubCwgcC5yLCBwLngpOwogICAgICAgIH0KICAgICAgICBpZiAocC50ID09IDIpIHsKICAgICAgICAgICAgdC0+ZGl2aWRlKHAubCwgcC54KTsKICAgICAgICB9CiAgICAgICAgaWYgKHAudCA9PSAzKSB7CiAgICAgICAgICAgIHByaW50ZigiJWRcbiIsIHQtPmdldChwLmwsIHAucikpOwogICAgICAgIH0KICAgIH0KCn0K