#include <bits/stdc++.h>
using namespace std;
const int L = 10, N = 100005;
int cnt[L], a[N], n, m, q, x, y, l, r, g[N], tot, fac[L][N * 16], opt;
struct Tree {
  int l, r, num, flag[L];
} T[N * 4];
int ksm(int x, int y) {
  int ans = 1;
  for (; y; y >>= 1, x = (long long)x * x % m)
    if (y & 1) ans = (long long)ans * x % m;
  return ans;
}
void solve(int x) {
  memset(cnt, 0, sizeof cnt);
  for (int i = 1; i <= tot; i++)
    while (x % g[i] == 0) cnt[i]++, x /= g[i];
  cnt[0] = x;
}
int calc(int x) {
  int s = T[x].num;
  for (int i = 1; i <= tot; i++) s = (long long)s * fac[i][T[x].flag[i]] % m;
  return s;
}
void build(int x, int l, int r) {
  T[x].l = l;
  T[x].r = r;
  T[x].flag[0] = 1;
  if (l == r) {
    solve(a[l]);
    T[x].num = cnt[0];
    for (int i = 1; i <= tot; i++) T[x].flag[i] = cnt[i];
    return;
  }
  int mid = (l + r) / 2;
  build(x * 2, l, mid);
  build(x * 2 + 1, mid + 1, r);
  T[x].num = (calc(x * 2) + calc(x * 2 + 1)) % m;
}
void add(int x, int y[]) {
  T[x].num = (long long)T[x].num * y[0] % m;
  T[x].flag[0] = (long long)T[x].flag[0] * y[0] % m;
  for (int i = 1; i <= tot; i++) T[x].flag[i] += y[i];
}
void down(int x) {
  add(x * 2, T[x].flag);
  add(x * 2 + 1, T[x].flag);
  T[x].flag[0] = 1;
  for (int i = 1; i <= tot; i++) T[x].flag[i] = 0;
}
void insert1(int x, int l, int r) {
  if (T[x].l > r || l > T[x].r) return;
  if (T[x].l >= l && T[x].r <= r) {
    add(x, cnt);
    return;
  }
  int t = calc(x);
  down(x);
  assert(t == (calc(x * 2) + calc(x * 2 + 1)) % m);
  insert1(x * 2, l, r);
  insert1(x * 2 + 1, l, r);
  T[x].num = (calc(x * 2) + calc(x * 2 + 1)) % m;
}
void insert2(int x, int y) {
  if (T[x].l == T[x].r) {
    T[x].num = (long long)T[x].num * cnt[0] % m;
    for (int i = 1; i <= tot; i++) T[x].flag[i] -= cnt[i];
    return;
  }
  down(x);
  int mid = (T[x].l + T[x].r) / 2;
  if (y <= mid)
    insert2(x * 2, y);
  else
    insert2(x * 2 + 1, y);
  T[x].num = (calc(x * 2) + calc(x * 2 + 1)) % m;
}
int find(int x, int l, int r) {
  if (T[x].l > r || l > T[x].r) return 0;
  if (T[x].l >= l && T[x].r <= r) return calc(x);
  down(x);
  T[x].num = (calc(x * 2) + calc(x * 2 + 1)) % m;
  return (find(x * 2, l, r) + find(x * 2 + 1, l, r)) % m;
}
int main() {
  scanf("%d%d", &n, &m);
  int phi = m, t = m;
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 2; i * i <= t; i++)
    if (t % i == 0) {
      g[++tot] = i;
      while (t % i == 0) t /= i;
      phi /= i;
      phi *= i - 1;
    }
  if (t != 1) g[++tot] = t, phi /= t, phi *= t - 1;
  scanf("%d", &q);
  for (int i = 1; i <= tot; i++) {
    fac[i][0] = 1;
    for (int j = 1; j <= 16 * (q + 1); j++)
      fac[i][j] = (long long)fac[i][j - 1] * g[i] % m;
  }
  build(1, 1, n);
  while (q--) {
    scanf("%d", &opt);
    if (opt == 1) {
      scanf("%d%d%d", &l, &r, &x);
      solve(x);
      insert1(1, l, r);
    }
    if (opt == 2) {
      scanf("%d%d", &x, &y);
      solve(y);
      cnt[0] = ksm(cnt[0], phi - 1);
      insert2(1, x);
    }
    if (opt == 3) {
      scanf("%d%d", &l, &r);
      printf("%d\n", find(1, l, r));
    }
  }
}
