#include <bits/stdc++.h>
template <typename _Tp>
inline bool Chkmax(_Tp& x, const _Tp& y) {
  return x < y ? x = y, true : false;
}
template <typename _Tp>
inline bool Chkmin(_Tp& x, const _Tp& y) {
  return x > y ? x = y, true : false;
}
const int maxN = 1e5 + 2;
int n, mod, q, cnt, phi, tmpl, tmpr, tmpval;
int a[maxN], quaf[10], tmp[10];
int sum[maxN << 2], L[maxN << 2], R[maxN << 2], fact[maxN << 2][10],
    rest[maxN << 2];
int power[10][maxN * 17];
inline void Mod(int& x) { x >= mod ? x -= mod : 0; }
inline int Modd(int x) { return x >= mod ? x - mod : x; }
inline void Modmul(int& x, int y) { x = (long long)x * y % mod; }
inline int QP(int a, int n) {
  if (a == 1) return 1;
  if (n == -1) return QP(a, phi - 1);
  int res = 1;
  while (n) {
    if (n & 1) res = (long long)res * a % mod;
    a = (long long)a * a % mod;
    n >>= 1;
  }
  return res;
}
inline void Split(int x, int* fac, int& res) {
  for (int i = 0; i < cnt; ++i) {
    fac[i] = 0;
    while (x % quaf[i] == 0) ++fac[i], x /= quaf[i];
  }
  res = x;
}
inline void Pushup(int x) { Mod(sum[x] = sum[x << 1] + sum[x << 1 | 1]); }
inline void Oper(int x, int* fac, int res) {
  for (int i = 0; i < cnt; ++i)
    Modmul(sum[x], power[i][fac[i]]), fact[x][i] += fac[i];
  if (res != 1) Modmul(sum[x], res), Modmul(rest[x], res);
}
inline void Pushdown(int x) {
  Oper(x << 1, fact[x], rest[x]);
  Oper(x << 1 | 1, fact[x], rest[x]);
  rest[x] = 1, memset(fact[x], 0, sizeof(fact[x]));
}
inline int Push(int pos) {
  int l = 1, r = n, curr = 1, mid;
  while (l < r) {
    Pushdown(curr);
    mid = (l + r) >> 1;
    if (pos <= mid)
      r = mid, curr <<= 1;
    else
      l = mid + 1, (curr <<= 1) |= 1;
  }
  return curr;
}
void Build(int curr, int l, int r) {
  L[curr] = l, R[curr] = r, rest[curr] = 1;
  if (l == r) {
    Split(a[l], fact[curr], rest[curr]);
    sum[curr] = a[l] % mod;
    return;
  }
  int mid = (l + r) >> 1;
  Build(curr << 1, l, mid), Build(curr << 1 | 1, mid + 1, r);
  Pushup(curr);
}
inline void Div(int pos, int x) {
  int curr = Push(pos);
  Split(x, tmp, x);
  sum[curr] = 1;
  for (int i = 0; i < cnt; ++i)
    Modmul(sum[curr], power[i][fact[curr][i] -= tmp[i]]);
  Modmul(rest[curr], QP(x, -1)), Modmul(sum[curr], rest[curr]);
  for (curr >>= 1; curr; curr >>= 1) Pushup(curr);
}
void Mul(int curr) {
  if (L[curr] >= tmpl and R[curr] <= tmpr) {
    Oper(curr, tmp, tmpval);
    return;
  }
  Pushdown(curr);
  int mid = (L[curr] + R[curr]) >> 1;
  if (tmpl <= mid) Mul(curr << 1);
  if (mid < tmpr) Mul(curr << 1 | 1);
  Pushup(curr);
}
int Query(int curr) {
  if (L[curr] > tmpr or R[curr] < tmpl) return 0;
  if (L[curr] >= tmpl and R[curr] <= tmpr) return sum[curr];
  Pushdown(curr);
  return Modd(Query(curr << 1) + Query(curr << 1 | 1));
}
int main() {
  scanf("%d %d", &n, &mod);
  tmpl = phi = mod;
  for (int i = 2; i * i <= tmpl; ++i)
    if (tmpl % i == 0) {
      quaf[cnt++] = i, (phi /= i) *= i - 1;
      while (tmpl % i == 0) tmpl /= i;
    }
  if (tmpl != 1) quaf[cnt++] = tmpl, (phi /= tmpl) *= tmpl - 1;
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  for (int i = 0; i < cnt; ++i) {
    power[i][0] = 1;
    for (int j = 1; j < 1700000; ++j)
      power[i][j] = (long long)power[i][j - 1] * quaf[i] % mod;
  }
  Build(1, 1, n);
  scanf("%d", &q);
  while (q--) {
    int opt;
    scanf("%d %d %d", &opt, &tmpl, &tmpr);
    switch (opt) {
      case 1:
        scanf("%d", &tmpval);
        Split(tmpval, tmp, tmpval);
        Mul(1);
        break;
      case 2:
        Div(tmpl, tmpr);
        break;
      case 3:
        printf("%d\n", Query(1));
        break;
      default:
        throw fprintf(stderr, "%d %d\n", q, opt);
    }
  }
  return 0;
}
