#include <bits/stdc++.h>
using namespace std;
int n, i, j, q, mod, NUM, DEG, flag, a[100005], t[100005 * 4];
long long f[100005 * 4], rv[100005];
vector<pair<int, int> > d[100005];
int mp[(1 << 18) + 5][20], val[20], num[100005], cnt;
vector<int> dg[20];
int POW(long long x, int n) {
  int ans = 1;
  while (n) {
    if (n & 1) ans = (ans * x) % mod;
    x = (x * x) % mod;
    n >>= 1;
  }
  return ans;
}
void gcd(int a, int b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return;
  }
  long long x1, rfvghdjk;
  gcd(b, a % b, x1, rfvghdjk);
  x = rfvghdjk;
  y = x1 - rfvghdjk * (a / b);
}
int rev(int a) {
  long long x, y;
  gcd(a, mod, x, y);
  return (x + mod * 1LL * mod) % mod;
}
void push(int v, bool ok) {
  if (!ok) return;
  int lf = v * 2, rg = v * 2 + 1;
  for (int i = 1; i <= cnt; i++) {
    if (!mp[v][i]) continue;
    long long pw = dg[i][mp[v][i]];
    t[lf] = (t[lf] * pw) % mod;
    t[rg] = (t[rg] * pw) % mod;
    mp[lf][i] += mp[v][i];
    mp[rg][i] += mp[v][i];
    mp[v][i] = 0;
  }
  if (f[v] > 1) {
    t[lf] = (t[lf] * f[v]) % mod;
    t[rg] = (t[rg] * f[v]) % mod;
    f[lf] = (f[lf] * f[v]) % mod;
    f[rg] = (f[rg] * f[v]) % mod;
    f[v] = 1;
  }
}
void upd(int v, int tl, int tr, int l, int r, long long x) {
  int m = (tl + tr) / 2;
  push(v, tl != tr);
  if (l > r) return;
  if (tl == l && tr == r) {
    t[v] = (t[v] * x) % mod;
    if (!flag)
      f[v] = (f[v] * x) % mod;
    else
      mp[v][NUM] += DEG;
    return;
  }
  upd(v * 2, tl, m, l, min(r, m), x);
  upd(v * 2 + 1, m + 1, tr, max(l, m + 1), r, x);
  t[v] = (t[v * 2] + t[v * 2 + 1]) % mod;
}
void upd2(int v, int tl, int tr, int pos, int x) {
  int m = (tl + tr) / 2, i;
  push(v, tl != tr);
  if (tl == tr) {
    for (i = 0; i < d[x].size(); i++) {
      int p = d[x][i].first, deg = d[x][i].second;
      if (!num[p])
        f[v] = (f[v] * POW(rv[p], deg)) % mod;
      else
        mp[v][num[p]] -= deg;
    }
    t[v] = f[v];
    for (i = 1; i <= cnt; i++) {
      if (!mp[v][i]) continue;
      t[v] = (t[v] * 1LL * dg[i][mp[v][i]]) % mod;
    }
    return;
  }
  if (pos <= m)
    upd2(v * 2, tl, m, pos, x);
  else
    upd2(v * 2 + 1, m + 1, tr, pos, x);
  push(v * 2, tl != m);
  push(v * 2 + 1, (m + 1) != tr);
  t[v] = (t[v * 2] + t[v * 2 + 1]) % mod;
}
int getSum(int v, int tl, int tr, int l, int r) {
  int m = (tl + tr) / 2;
  push(v, tl != tr);
  if (l > r) return 0;
  if (tl == l && tr == r) return t[v] % mod;
  return (getSum(v * 2, tl, m, l, min(r, m)) +
          getSum(v * 2 + 1, m + 1, tr, max(l, m + 1), r)) %
         mod;
}
void build(int v, int tl, int tr) {
  int m = (tl + tr) / 2, i;
  if (tl == tr) {
    for (i = 0; i < d[a[tl]].size(); i++) {
      int p = d[a[tl]][i].first, deg = d[a[tl]][i].second;
      if (num[p])
        mp[v][num[p]] += deg;
      else
        f[v] = f[v] * POW(p, deg);
    }
    t[v] = a[tl];
    return;
  }
  build(v * 2, tl, m);
  build(v * 2 + 1, m + 1, tr);
  t[v] = (t[v * 2] + t[v * 2 + 1]) % mod;
}
int main() {
  ios_base ::sync_with_stdio();
  cin.tie(0);
  scanf("%d%d", &n, &mod);
  for (i = 2; i <= 100000; i++) {
    if (d[i].size() == 0) {
      for (j = 1; j * i <= 100000; j++) {
        int x = j * i, sm = 0;
        while (x % i == 0) {
          sm++;
          x /= i;
        }
        d[i * j].push_back({i, sm});
      }
      if (mod % i == 0)
        num[i] = ++cnt, val[cnt] = i;
      else
        rv[i] = rev(i);
    }
  }
  for (i = 1; i <= cnt; i++) {
    int pw = 1, sm = 0;
    while (pw <= 100000) pw *= val[i], sm++;
    pw = 1;
    for (j = 0; j <= (n + q) * sm; j++) {
      dg[i].push_back(pw);
      pw = (pw * 1LL * val[i]) % mod;
    }
  }
  fill(f, f + 4 * n, 1);
  for (i = 0; i < n; i++) scanf("%d", &a[i]);
  build(1, 0, n - 1);
  scanf("%d", &q);
  while (q--) {
    int type, l, r, x, pos;
    scanf("%d", &type);
    if (type == 3) {
      scanf("%d%d", &l, &r);
      l--;
      r--;
      printf("%d\n", getSum(1, 0, n - 1, l, r));
    }
    if (type == 1) {
      scanf("%d%d%d", &l, &r, &x);
      l--;
      r--;
      for (i = 0; i < d[x].size(); i++) {
        if (num[d[x][i].first]) {
          flag = 1;
          NUM = num[d[x][i].first];
          DEG = d[x][i].second;
          upd(1, 0, n - 1, l, r, dg[NUM][d[x][i].second]);
        } else {
          flag = 0;
          upd(1, 0, n - 1, l, r, POW(d[x][i].first, d[x][i].second));
        }
      }
    }
    if (type == 2) {
      scanf("%d%d", &pos, &x);
      pos--;
      upd2(1, 0, n - 1, pos, x);
    }
  }
  return 0;
}
