#include <bits/stdc++.h>
using namespace std;
template <typename T>
void chkmax(T &x, T y) {
  x = x > y ? x : y;
}
template <typename T>
void chkmin(T &x, T y) {
  x = x > y ? y : x;
}
template <typename T>
void update(T &x, T y, T mod) {
  x = x + y > mod ? x + y - mod : x + y;
}
template <typename T>
void multi(T &x, T y, T mod) {
  x = 1ll * x * y % mod;
}
const int INF = (1ll << 30);
template <typename T>
void read(T &x) {
  x = 0;
  bool f = 1;
  char ch;
  do {
    ch = getchar();
    if (ch == '-') f = 0;
  } while (ch > '9' || ch < '0');
  do {
    x = x * 10 + ch - '0';
    ch = getchar();
  } while (ch >= '0' && ch <= '9');
  x = f ? x : -x;
}
template <typename T>
void write(T x) {
  if (x < 0) x = ~x + 1, putchar('-');
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
const int N = 1e5 + 7;
struct Segment_Tree {
  int l, r, sum, rem, mul, fac[20];
} t[N << 2];
int n, m, mod, cnt, tot, phi, a[N], P[N], tmp[N], prime[N];
bool vis[N];
inline int calc(int x) {
  for (int i = 1; i <= tot; i++) {
    tmp[i] = 0;
    while (x % P[i] == 0) {
      x /= P[i];
      tmp[i]++;
    }
  }
  return x;
}
inline int qpow(int a, int b) {
  long long ret = 1;
  while (b) {
    if (b & 1) ret = 1ll * ret * a % mod;
    a = 1ll * a * a % mod;
    b >>= 1;
  }
  return ret % mod;
}
inline void mul(int p, int mul, int rem, int *tmp) {
  multi(t[p].rem, rem, mod);
  for (int i = 1; i <= tot; i++) t[p].fac[i] += tmp[i];
  multi(t[p].sum, mul, mod);
  multi(t[p].mul, mul, mod);
}
inline void divide(int p, int y, int *tmp) {
  multi(t[p].rem, qpow(y, phi - 1), mod);
  int tp = t[p].rem;
  for (int i = 1; i <= tot; i++) {
    t[p].fac[i] -= tmp[i];
    multi(tp, qpow(P[i], t[p].fac[i]), mod);
  }
  t[p].sum = tp % mod;
}
inline void pushdown(int p) {
  if (t[p].mul != 1 || t[p].rem != 1) {
    mul((p << 1), t[p].mul, t[p].rem, t[p].fac);
    mul((p << 1 | 1), t[p].mul, t[p].rem, t[p].fac);
    t[p].mul = t[p].rem = 1;
    for (int i = 1; i <= tot; i++) t[p].fac[i] = 0;
  }
}
inline void build(int p, int l, int r) {
  t[p].l = l;
  t[p].r = r;
  t[p].mul = t[p].rem = 1;
  if (l == r) {
    t[p].sum = a[l] % mod;
    t[p].rem = calc(a[l]);
    for (int i = 1; i <= tot; i++) t[p].fac[i] = tmp[i];
    return;
  }
  pushdown(p);
  int mid = (t[p].l + t[p].r) >> 1;
  build((p << 1), l, mid);
  build((p << 1 | 1), mid + 1, r);
  t[p].sum = (t[(p << 1)].sum + t[(p << 1 | 1)].sum) % mod;
}
inline void multi(int p, int l, int r, int x, int k, int *tmp) {
  if (l <= t[p].l && t[p].r <= r) {
    mul(p, k, x, tmp);
    return;
  }
  pushdown(p);
  int mid = (t[p].l + t[p].r) >> 1;
  if (l <= mid) multi((p << 1), l, r, x, k, tmp);
  if (r > mid) multi((p << 1 | 1), l, r, x, k, tmp);
  t[p].sum = (t[(p << 1)].sum + t[(p << 1 | 1)].sum) % mod;
}
inline void divide(int p, int x, int y, int *tmp) {
  if (t[p].l == t[p].r) {
    divide(p, y, tmp);
    return;
  }
  pushdown(p);
  int mid = (t[p].l + t[p].r) >> 1;
  if (x <= mid)
    divide((p << 1), x, y, tmp);
  else
    divide((p << 1 | 1), x, y, tmp);
  t[p].sum = (t[(p << 1)].sum + t[(p << 1 | 1)].sum) % mod;
}
inline int query(int p, int l, int r) {
  if (l <= t[p].l && t[p].r <= r) return t[p].sum;
  pushdown(p);
  int mid = (t[p].l + t[p].r) >> 1, ans = 0;
  if (l <= mid) update(ans, query((p << 1), l, r), mod);
  if (r > mid) update(ans, query((p << 1 | 1), l, r), mod);
  return ans;
}
inline void init(int NN) {
  for (int i = 2; i <= NN; i++) {
    if (!vis[i]) {
      prime[++cnt] = i;
    }
    for (int j = 1; j <= cnt && prime[j] * i <= NN; j++) {
      vis[i * prime[j]] = true;
      if (i % prime[j] == 0) break;
    }
  }
}
inline int getphi(int x) {
  int ans = x;
  for (int i = 1; i <= cnt && prime[i] * prime[i] <= x; i++) {
    if (x % prime[i] == 0) {
      ans = 1ll * ans * (prime[i] - 1) / prime[i];
      while (x % prime[i] == 0) x /= prime[i];
    }
  }
  if (x != 1) ans = 1ll * ans * (x - 1) / x;
  return ans;
}
inline void divide(int x) {
  for (int i = 1; i <= cnt && prime[i] * prime[i] <= x; i++) {
    if (x % prime[i] == 0) {
      while (x % prime[i] == 0) x /= prime[i];
      P[++tot] = prime[i];
    }
  }
  if (x != 1) P[++tot] = x;
}
int main() {
  read(n);
  read(mod);
  init(1e5);
  divide(mod);
  phi = getphi(mod);
  for (int i = 1; i <= n; i++) read(a[i]);
  build(1, 1, n);
  read(m);
  for (int i = 1, opt, l, r, x; i <= m; i++) {
    read(opt);
    if (opt == 1) {
      read(l);
      read(r);
      read(x);
      multi(1, l, r, calc(x), x, tmp);
    }
    if (opt == 2) {
      read(l);
      read(x);
      divide(1, l, calc(x), tmp);
    }
    if (opt == 3) {
      read(l);
      read(r);
      printf("%d\n", query(1, l, r) % mod);
    }
  }
  return 0;
}
