#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
int n, k, q, mod, phi;
int a[N], pf[11], lpf[N], cow[11][N * 16];
unordered_map<int, int> idx;
int lp[N * 4], tp[N * 4], t[N * 4];
array<int, 11> lc[N * 4], tc[N * 4];
template <class T, class... Ts>
int add(T f) {
  return f;
}
template <class T, class... Ts>
int add(T f, Ts... ts) {
  return (f + add(ts...)) % mod;
}
template <class T, class... Ts>
int sub(T f) {
  return f;
}
template <class T, class... Ts>
int sub(T f, Ts... ts) {
  return (f - sub(ts...) + 1ll * mod * mod) % mod;
}
template <class T, class... Ts>
int mul(T f) {
  return f;
}
template <class T, class... Ts>
int mul(T f, Ts... ts) {
  return (1ll * f * mul(ts...)) % mod;
}
int binpow(int n, int k) {
  int ans = 1;
  while (k) {
    if (k & 1) ans = mul(ans, n);
    n = mul(n, n), k >>= 1;
  }
  return ans;
}
int inv(int n) { return binpow(n, phi - 1); }
void push(int i, int l, int r) {
  t[i] = mul(t[i], lp[i]);
  tp[i] = mul(tp[i], lp[i]);
  for (int j = 0; j < k; j++) {
    t[i] = mul(t[i], cow[j][lc[i][j]]);
    tc[i][j] += lc[i][j];
  }
  if (l < r) {
    lp[i * 2] = mul(lp[i * 2], lp[i]);
    lp[i * 2 + 1] = mul(lp[i * 2 + 1], lp[i]);
    for (int j = 0; j < k; j++) {
      lc[i * 2][j] += lc[i][j];
      lc[i * 2 + 1][j] += lc[i][j];
    }
  }
  for (int j = 0; j < k; j++) lc[i][j] = 0;
  lp[i] = 1;
}
void upd(int L, int R, int P, array<int, 11> &C, int i = 1, int l = 1,
         int r = n) {
  push(i, l, r);
  if (r < L || l > R) return;
  if (L <= l && r <= R) {
    lp[i] = P, lc[i] = C;
    push(i, l, r);
    return;
  }
  int m = (l + r) / 2;
  upd(L, R, P, C, i * 2, l, m);
  upd(L, R, P, C, i * 2 + 1, m + 1, r);
  t[i] = add(t[i * 2], t[i * 2 + 1]);
}
void upd(int l, int r, int x) {
  int pr = 1;
  array<int, 11> co{};
  while (x != 1) {
    int y = lpf[x], c = 0;
    while (x % y == 0) x /= y, c++;
    if (mod % y == 0)
      co[idx[y]] = c;
    else
      pr = mul(pr, binpow(y, c));
  }
  upd(l, r, pr, co);
}
void div(int I, int P, array<int, 11> &C, int i = 1, int l = 1, int r = n) {
  push(i, l, r);
  if (r < I || l > I) return;
  if (l == r) {
    tp[i] = mul(tp[i], P);
    for (int j = 0; j < k; j++) tc[i][j] -= C[j];
    t[i] = tp[i];
    for (int j = 0; j < k; j++) t[i] = mul(t[i], cow[j][tc[i][j]]);
    return;
  }
  int m = (l + r) / 2;
  div(I, P, C, i * 2, l, m);
  div(I, P, C, i * 2 + 1, m + 1, r);
  t[i] = add(t[i * 2], t[i * 2 + 1]);
}
void upd(int i, int x) {
  int pr = 1;
  array<int, 11> co{};
  while (x != 1) {
    int y = lpf[x], c = 0;
    while (x % y == 0) x /= y, c++;
    if (mod % y == 0)
      co[idx[y]] = c;
    else
      pr = mul(pr, binpow(y, c));
  }
  div(i, inv(pr), co);
}
int que(int L, int R, int i = 1, int l = 1, int r = n) {
  push(i, l, r);
  if (r < L || l > R) return 0;
  if (L <= l && r <= R) return t[i];
  int m = (l + r) / 2;
  return add(que(L, R, i * 2, l, m), que(L, R, i * 2 + 1, m + 1, r));
}
int32_t main() {
  cin.tie(0)->sync_with_stdio(0);
  for (int i = 2; i < N; i++) {
    if (lpf[i]) continue;
    for (int j = i; j < N; j += i) {
      if (!lpf[j]) lpf[j] = i;
    }
  }
  for (int i = 0; i < N * 4; i++) {
    t[i] = lp[i] = tp[i] = 1;
  }
  cin >> n >> mod;
  int x = mod;
  phi = mod;
  int s = sqrt(mod);
  for (int y = 2; y <= s; y++) {
    if (x % y == 0) {
      phi -= phi / y;
      cow[k][0] = 1;
      for (int i = 1; i < N * 16; i++) {
        cow[k][i] = mul(cow[k][i - 1], y);
      }
      pf[k] = y, idx[y] = k++;
      while (x % y == 0) x /= y;
    }
  }
  if (x != 1) {
    phi -= phi / x;
    for (int i = 0; i < N * 16; i++) cow[k][i] = binpow(x, i);
    pf[k] = x, idx[x] = k++;
  }
  for (int i = 1; i <= n; i++) cin >> a[i], upd(i, i, a[i]);
  cin >> q;
  while (q--) {
    int t, l, r, p, x;
    cin >> t;
    if (t == 1) cin >> l >> r >> x, upd(l, r, x);
    if (t == 2) cin >> p >> x, upd(p, x);
    if (t == 3) cin >> l >> r, cout << que(l, r) << '\n';
  }
}
