#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const long double pi = acos(-1.0);
const int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int digarr[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
const int alf = 26;
const int dig = 10;
const int two = 2;
const int th = 3;
const long long prost = 239;
const long long bt = 31;
const long double eps = 1e-8;
const long long INF = 1e18 + 239;
const int BIG = 1e9 + 239;
const long long MOD = 1e9 + 7;
const long long MOD2 = (long long)MOD * (long long)MOD;
mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int M = 1e5 + 239;
const int N = 2e3 + 239;
const int L = 12;
const int T = (1 << 18);
const int B = trunc(sqrt(M)) + 1;
const int X = 2e6 + 239;
long long inv(long long a, long long m) {
  if (a == 1) return 1;
  return ((1 - inv(m % a, a) * m) / a) + m;
}
int n, m, p[L], c, sx[L];
int v[L][T], av[L][T], sum[T], add[T];
void build(int i, int l, int r) {
  for (int x = 0; x < c; x++) {
    v[x][i] = 0;
    av[x][i] = 0;
  }
  add[i] = 1;
  if (r - l == 1) {
    sum[i] = 1;
    return;
  }
  int mid = (l + r) >> 1;
  build(2 * i + 1, l, mid);
  build(2 * i + 2, mid, r);
  sum[i] = sum[2 * i + 1] + sum[2 * i + 2];
  if (sum[i] >= m) sum[i] -= m;
}
void push(int i, int l, int r) {
  sum[i] = ((long long)sum[i] * (long long)add[i]) % (long long)m;
  if (r - l != 1) {
    for (int x = 0; x < c; x++) {
      av[x][2 * i + 1] += av[x][i];
      av[x][2 * i + 2] += av[x][i];
    }
    add[2 * i + 1] =
        ((long long)add[2 * i + 1] * (long long)add[i]) % (long long)m;
    add[2 * i + 2] =
        ((long long)add[2 * i + 2] * (long long)add[i]) % (long long)m;
  } else {
    for (int x = 0; x < c; x++) v[x][i] += av[x][i];
  }
  add[i] = 1;
  for (int x = 0; x < c; x++) av[x][i] = 0;
}
void upd(int i, int l, int r, int ql, int qr, int um) {
  push(i, l, r);
  if (qr <= l || r <= ql) return;
  if (ql <= l && r <= qr) {
    for (int x = 0; x < c; x++) av[x][i] += sx[x];
    add[i] = ((long long)add[i] * (long long)um) % (long long)m;
    push(i, l, r);
    return;
  }
  int mid = (l + r) >> 1;
  upd(2 * i + 1, l, mid, ql, qr, um);
  upd(2 * i + 2, mid, r, ql, qr, um);
  sum[i] = sum[2 * i + 1] + sum[2 * i + 2];
  if (sum[i] >= m) sum[i] -= m;
}
void change(int i, int l, int r, int p, int x) {
  push(i, l, r);
  if (p < l || r <= p) return;
  if (r - l == 1) {
    for (int x = 0; x < c; x++) v[x][i] = sx[x];
    sum[i] = x;
    return;
  }
  int mid = (l + r) >> 1;
  change(2 * i + 1, l, mid, p, x);
  change(2 * i + 2, mid, r, p, x);
  sum[i] = sum[2 * i + 1] + sum[2 * i + 2];
  if (sum[i] >= m) sum[i] -= m;
}
int getsum(int i, int l, int r, int ql, int qr) {
  push(i, l, r);
  if (qr <= l || r <= ql) return 0;
  if (ql <= l && r <= qr) return sum[i];
  int mid = (l + r) >> 1;
  int ans =
      getsum(2 * i + 1, l, mid, ql, qr) + getsum(2 * i + 2, mid, r, ql, qr);
  if (ans >= m) ans -= m;
  return ans;
}
void fndpw(int i, int l, int r, int p) {
  push(i, l, r);
  if (p < l || r <= p) return;
  if (r - l == 1) {
    for (int x = 0; x < c; x++) sx[x] = v[x][i];
    return;
  }
  int mid = (l + r) >> 1;
  fndpw(2 * i + 1, l, mid, p);
  fndpw(2 * i + 2, mid, r, p);
}
int pr[T], ap[T];
void push_vs(int i, int l, int r) {
  pr[i] = ((long long)pr[i] * (long long)ap[i]) % (long long)m;
  if (r - l != 1) {
    ap[2 * i + 1] =
        ((long long)ap[2 * i + 1] * (long long)ap[i]) % (long long)m;
    ap[2 * i + 2] =
        ((long long)ap[2 * i + 2] * (long long)ap[i]) % (long long)m;
  }
  ap[i] = 1;
}
void build_vs(int i, int l, int r) {
  ap[i] = 1;
  if (r - l == 1) {
    pr[i] = 1;
    return;
  }
  int mid = (l + r) >> 1;
  build_vs(2 * i + 1, l, mid);
  build_vs(2 * i + 2, mid, r);
  pr[i] = pr[2 * i + 1] + pr[2 * i + 2];
  if (pr[i] >= m) pr[i] -= m;
}
void upd_vs(int i, int l, int r, int ql, int qr, int um) {
  push_vs(i, l, r);
  if (qr <= l || r <= ql) return;
  if (ql <= l && r <= qr) {
    ap[i] = ((long long)ap[i] * (long long)um) % (long long)m;
    push_vs(i, l, r);
    return;
  }
  int mid = (l + r) >> 1;
  upd_vs(2 * i + 1, l, mid, ql, qr, um);
  upd_vs(2 * i + 2, mid, r, ql, qr, um);
  pr[i] = pr[2 * i + 1] + pr[2 * i + 2];
  if (pr[i] >= m) pr[i] -= m;
}
int getvs(int i, int l, int r, int p) {
  push_vs(i, l, r);
  if (r - l == 1) return pr[i];
  int mid = (l + r) >> 1;
  if (p < mid)
    return getvs(2 * i + 1, l, mid, p);
  else
    return getvs(2 * i + 2, mid, r, p);
}
inline int power(int a, int k) {
  if (k == 0) return 1;
  int t = power(a, k >> 1);
  t = ((long long)t * (long long)t) % (long long)m;
  if (k & 1) t = ((long long)t * (long long)a) % (long long)m;
  return t;
}
int rt[L];
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  c = 0;
  int mm = m;
  for (int i = 2; i * i <= m; i++)
    if (mm % i == 0) {
      p[c++] = i;
      while (mm % i == 0) mm /= i;
    }
  if (mm > 1) p[c++] = mm;
  build(0, 0, n);
  build_vs(0, 0, n);
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    int aa = a;
    for (int x = 0; x < c; x++) {
      sx[x] = 0;
      while (a % p[x] == 0) {
        sx[x]++;
        a /= p[x];
      }
    }
    change(0, 0, n, i, aa);
    upd_vs(0, 0, n, i, i + 1, a);
  }
  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    int tp, l, r, t;
    cin >> tp;
    if (tp == 1) {
      cin >> l >> r >> t;
      l--, r--;
      int tt = t;
      for (int x = 0; x < c; x++) {
        sx[x] = 0;
        while (t % p[x] == 0) {
          sx[x]++;
          t /= p[x];
        }
      }
      upd(0, 0, n, l, r + 1, tt);
      upd_vs(0, 0, n, l, r + 1, t);
    } else if (tp == 2) {
      cin >> l >> t;
      l--;
      fndpw(0, 0, n, l);
      int u = getvs(0, 0, n, l);
      for (int x = 0; x < c; x++)
        while (t % p[x] == 0) {
          sx[x]--;
          t /= p[x];
        }
      t = inv(t, m);
      upd_vs(0, 0, n, l, l + 1, t);
      u = ((long long)u * (long long)t) % (long long)m;
      for (int x = 0; x < c; x++)
        u = ((long long)u * (long long)power(p[x], sx[x])) % (long long)m;
      change(0, 0, n, l, u);
    } else {
      cin >> l >> r;
      l--, r--;
      cout << getsum(0, 0, n, l, r + 1) << "\n";
    }
  }
  return 0;
}
