#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x * f;
}
const int maxn = 1e5 + 10;
int n, mod, a[maxn], q, prime[maxn], pcnt, mark[maxn];
inline int mul(int x, int y) { return (long long)x * y % mod; }
inline int inc(int x, int y) {
  x += y;
  return x >= mod ? x - mod : x;
}
inline int qpow(int x, int y) {
  int res = 1;
  for (; y; y >>= 1, x = (long long)x * x % mod)
    if (y & 1) res = (long long)res * x % mod;
  return res;
}
void init(int n) {
  mark[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (!mark[i]) prime[++pcnt] = i;
    for (int j = 1; j <= pcnt; j++) {
      int np = prime[j], now = i * np;
      if (now > n) break;
      mark[now] = 1;
      if (i % np == 0) break;
    }
  }
}
int fac[10], fac_cnt, sim[maxn];
void divide(int x) {
  for (int i = 1; i <= pcnt; i++) {
    int np = prime[i];
    if (np * np > x) break;
    if (x % np == 0) {
      x /= np, fac[++fac_cnt] = np;
      while (x % np == 0) x /= np;
    }
  }
  if (x > 1) fac[++fac_cnt] = x;
}
struct SegmentTree {
  int sum[maxn << 2], tag[maxn << 2];
  inline void update(int x) { sum[x] = inc(sum[(x << 1)], sum[(x << 1 | 1)]); }
  inline void operate(int x, int v) {
    sum[x] = mul(sum[x], v), tag[x] = mul(tag[x], v);
  }
  inline void pushdown(int x) {
    if (tag[x] != 1) {
      int v = tag[x];
      operate((x << 1), v);
      operate((x << 1 | 1), v);
      tag[x] = 1;
    }
  }
  inline void build(int x, int l, int r) {
    tag[x] = 1;
    if (l == r) {
      sum[x] = a[l] % mod;
      return;
    }
    int mid = (l + r) >> 1;
    build((x << 1), l, mid);
    build((x << 1 | 1), mid + 1, r);
    update(x);
  }
  inline void build2(int x, int l, int r) {
    tag[x] = 1;
    if (l == r) {
      sum[x] = sim[l] % mod;
      return;
    }
    int mid = (l + r) >> 1;
    build2((x << 1), l, mid);
    build2((x << 1 | 1), mid + 1, r);
    update(x);
  }
  inline void modify(int x, int l, int r, int lx, int rx, int v) {
    if (l >= lx && r <= rx) return operate(x, v);
    int mid = (l + r) >> 1;
    pushdown(x);
    if (lx <= mid) modify((x << 1), l, mid, lx, rx, v);
    if (rx > mid) modify((x << 1 | 1), mid + 1, r, lx, rx, v);
    update(x);
  }
  inline void modify(int x, int l, int r, int pos, int v) {
    if (l == r) {
      sum[x] = v;
      return;
    }
    int mid = (l + r) >> 1;
    pushdown(x);
    if (pos <= mid)
      modify((x << 1), l, mid, pos, v);
    else
      modify((x << 1 | 1), mid + 1, r, pos, v);
    update(x);
  }
  inline int query(int x, int l, int r, int lx, int rx) {
    if (l >= lx && r <= rx) return sum[x];
    int mid = (l + r) >> 1, res = 0;
    pushdown(x);
    if (lx <= mid) res = inc(res, query((x << 1), l, mid, lx, rx));
    if (rx > mid) res = inc(res, query((x << 1 | 1), mid + 1, r, lx, rx));
    return res;
  }
} t1, t2;
struct mybit {
  int t[maxn];
  mybit() {}
  inline void add(int x, int v) {
    for (; x <= n; x += (x & -x)) t[x] += v;
  }
  inline void add(int l, int r, int v) { add(l, v), add(r + 1, -v); }
  inline int sum(int x) {
    int s = 0;
    for (; x; x -= (x & -x)) s += t[x];
    return s;
  }
} bit[10];
void exgcd(int a, int b, int &x, int &y) {
  if (!b) {
    x = 1, y = 0;
    return;
  }
  exgcd(b, a % b, y, x);
  y -= a / b * x;
}
int main() {
  n = read(), mod = read(), init(100000), divide(mod);
  for (int i = 1; i <= n; i++) a[i] = read();
  t1.build(1, 1, n);
  memcpy(sim, a, 4 * (n + 2));
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= fac_cnt; j++) {
      int np = fac[j];
      if (sim[i] % np) continue;
      int y = 1;
      sim[i] /= np;
      while (sim[i] % np == 0) sim[i] /= np, y++;
      bit[j].add(i, i, y);
    }
  t2.build2(1, 1, n);
  q = read();
  while (q--) {
    int opt = read();
    if (opt == 1) {
      int l = read(), r = read(), x = read();
      t1.modify(1, 1, n, l, r, x);
      for (int j = 1; j <= fac_cnt; j++) {
        int np = fac[j];
        if (x % np) continue;
        int y = 1;
        x /= np;
        while (x % np == 0) x /= np, y++;
        bit[j].add(l, r, y);
      }
      t2.modify(1, 1, n, l, r, x);
    } else if (opt == 2) {
      int p = read(), x = read();
      for (int j = 1; j <= fac_cnt; j++) {
        int np = fac[j];
        if (x % np) continue;
        int y = 1;
        x /= np;
        while (x % np == 0) x /= np, y++;
        bit[j].add(p, p, -y);
      }
      int inv, tmp;
      exgcd(x, mod, inv, tmp);
      inv %= mod;
      if (inv < 0) inv += mod;
      t2.modify(1, 1, n, p, p, inv);
      int now = t2.query(1, 1, n, p, p);
      for (int j = 1; j <= fac_cnt; j++) {
        int np = fac[j], y = bit[j].sum(p);
        now = mul(now, qpow(np, y));
      }
      t1.modify(1, 1, n, p, now);
    } else {
      int l = read(), r = read();
      printf("%d\n", t1.query(1, 1, n, l, r));
    }
  }
  return 0;
}
