#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010, N = 20;
int m, p[N], b[maxn], tot, q[N];
long long Phi;
inline long long qpow(long long a, long long b) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = (ans * a) % m;
    a = a * a % m;
    b >>= 1;
  }
  return ans;
}
inline long long phi(long long n) {
  long long ans = n;
  for (register int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      ans = ans / i * (i - 1);
      p[tot++] = i;
      while (n % i == 0) n /= i;
    }
  }
  if (n > 1) {
    p[tot++] = n;
    ans = ans / n * (n - 1);
  }
  return ans;
}
struct STe {
  long long r, rt;
  long long tg, s;
  long long a[N], fl[N];
} tr[maxn << 2];
inline void pushup(int o) {
  tr[o].s = (tr[(o << 1)].s + tr[((o << 1) | 1)].s) % m;
}
inline void pushdown(int o) {
  if (tr[o].rt != 1) {
    tr[(o << 1)].r = (tr[(o << 1)].r * tr[o].rt) % m;
    tr[(o << 1)].rt = (tr[(o << 1)].rt * tr[o].rt) % m;
    tr[((o << 1) | 1)].r = (tr[((o << 1) | 1)].r * tr[o].rt) % m;
    tr[((o << 1) | 1)].rt = (tr[((o << 1) | 1)].rt * tr[o].rt) % m;
    tr[o].rt = 1;
  }
  if (tr[o].tg != 1) {
    tr[(o << 1)].s = (tr[(o << 1)].s * tr[o].tg) % m;
    tr[(o << 1)].tg = (tr[(o << 1)].tg * tr[o].tg) % m;
    tr[((o << 1) | 1)].s = (tr[((o << 1) | 1)].s * tr[o].tg) % m;
    tr[((o << 1) | 1)].tg = (tr[((o << 1) | 1)].tg * tr[o].tg) % m;
    tr[o].tg = 1;
  }
  for (register int i = 0; i < tot; i++) {
    tr[(o << 1)].a[i] = (tr[(o << 1)].a[i] + tr[o].fl[i]);
    tr[(o << 1)].fl[i] = (tr[(o << 1)].fl[i] + tr[o].fl[i]);
    tr[((o << 1) | 1)].a[i] = (tr[((o << 1) | 1)].a[i] + tr[o].fl[i]);
    tr[((o << 1) | 1)].fl[i] = (tr[((o << 1) | 1)].fl[i] + tr[o].fl[i]);
    tr[o].fl[i] = 0;
  }
}
void build(int o, int l, int r) {
  tr[o].r = tr[o].tg = tr[o].s = tr[o].rt = 1;
  memset(tr[o].a, 0, sizeof(tr[o].a));
  memset(tr[o].fl, 0, sizeof(tr[o].fl));
  if (l == r) {
    tr[o].s = b[l] % m;
    for (register int i = 0; i < tot; i++) {
      while (b[l] % p[i] == 0) {
        b[l] /= p[i];
        tr[o].a[i]++;
      }
    }
    tr[o].r = b[l] % m;
    return;
  }
  int mid = (l + r) >> 1;
  build((o << 1), l, mid);
  build(((o << 1) | 1), mid + 1, r);
  pushup(o);
}
void mul(int o, int l, int r, int ql, int qr, long long x, long long y) {
  if (l >= ql && r <= qr) {
    tr[o].s = (tr[o].s * x) % m;
    tr[o].tg = (tr[o].tg * x) % m;
    tr[o].r = (tr[o].r * y) % m;
    tr[o].rt = (tr[o].rt * y) % m;
    for (register int i = 0; i < tot; i++) {
      tr[o].fl[i] += q[i];
      tr[o].a[i] += q[i];
    }
    return;
  }
  pushdown(o);
  int mid = (l + r) >> 1;
  if (ql <= mid) mul((o << 1), l, mid, ql, qr, x, y);
  if (qr > mid) mul(((o << 1) | 1), mid + 1, r, ql, qr, x, y);
  pushup(o);
}
long long query(int o, int l, int r, int ql, int qr) {
  if (l >= ql && r <= qr) return tr[o].s;
  pushdown(o);
  int mid = (l + r) >> 1;
  long long ans = 0;
  if (ql <= mid) ans = (ans + query((o << 1), l, mid, ql, qr)) % m;
  if (qr > mid) ans = (ans + query(((o << 1) | 1), mid + 1, r, ql, qr)) % m;
  return ans;
}
void divide(int o, int l, int r, int pos, long long y) {
  if (l == r) {
    for (register int i = 0; i < tot; i++) {
      while (y % p[i] == 0) y /= p[i], tr[o].a[i]--;
    }
    tr[o].r = (tr[o].r * qpow(y, Phi - 1)) % m;
    tr[o].s = tr[o].r;
    for (register int i = 0; i < tot; i++)
      tr[o].s = (tr[o].s * qpow(p[i], tr[o].a[i])) % m;
    return;
  }
  pushdown(o);
  int mid = (l + r) >> 1;
  if (pos <= mid)
    divide((o << 1), l, mid, pos, y);
  else
    divide(((o << 1) | 1), mid + 1, r, pos, y);
  pushup(o);
}
int main() {
  int n;
  scanf("%d%lld", &n, &m);
  Phi = phi(m);
  for (register int i = 1; i <= n; i++) {
    scanf("%d", &b[i]);
  }
  int t, op, x, y, z;
  build(1, 1, n);
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &op);
    if (op == 1) {
      scanf("%d%d%d", &x, &y, &z);
      int tmp = z;
      for (register int i = 0; i < tot; i++) {
        q[i] = 0;
        while (tmp % p[i] == 0) {
          tmp /= p[i];
          q[i]++;
        }
      }
      mul(1, 1, n, x, y, z, tmp);
    } else if (op == 2) {
      scanf("%d%d", &x, &y);
      divide(1, 1, n, x, y);
    } else {
      scanf("%d%d", &x, &y);
      printf("%lld\n", query(1, 1, n, x, y));
    }
  }
}
