#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct node {
  long long sum, x, y, cnt[10];
  node() {
    sum = 0;
    x = y = 1;
    memset(cnt, 0, sizeof cnt);
  }
};
long long pw[10][20 * N], n, mod;
vector<long long> P;
node seg[4 * N], A, B;
long long Pow(long long a, long long b) {
  long long res = 1;
  for (; b; b >>= 1) res = res * (b & 1 ? a : 1) % mod, a = a * a % mod;
  return res;
}
void fac(int t, node &C) {
  C.sum = 0;
  memset(C.cnt, 0, sizeof C.cnt);
  C.y = t % mod;
  for (int i = 0; i < (int)(P.size()); i++)
    while (t % P[i] == 0) t /= P[i], C.cnt[i]++;
  C.x = t % mod;
}
void push(node &X, node Y) {
  X.sum = X.sum * Y.y % mod;
  X.x = X.x * Y.x % mod;
  X.y = X.y * Y.y % mod;
  for (int i = 0; i < 10; i++) X.cnt[i] += Y.cnt[i];
}
void shift(int id) {
  push(seg[id << 1], seg[id]);
  push(seg[id << 1 | 1], seg[id]);
  seg[id].x = seg[id].y = 1;
  memset(seg[id].cnt, 0, sizeof seg[id].cnt);
  return;
}
void modify(int p, int l = 0, int r = n, int id = 1) {
  if (r - l == 1) {
    seg[id] = A;
    seg[id].sum = A.y;
    return;
  }
  shift(id);
  int md = (l + r) >> 1;
  if (p < md)
    modify(p, l, md, id << 1);
  else
    modify(p, md, r, id << 1 | 1);
  seg[id].sum = (seg[id << 1].sum + seg[id << 1 | 1].sum) % mod;
}
void upd(int l, int r, int s = 0, int e = n, int id = 1) {
  if (e <= l || r <= s) return;
  if (l <= s && e <= r) {
    push(seg[id], A);
    return;
  }
  shift(id);
  int md = (s + e) >> 1;
  upd(l, r, s, md, id << 1);
  upd(l, r, md, e, id << 1 | 1);
  seg[id].sum = (seg[id << 1].sum + seg[id << 1 | 1].sum) % mod;
}
node get(int p, int l = 0, int r = n, int id = 1) {
  if (r - l == 1) return seg[id];
  shift(id);
  int md = (l + r) >> 1;
  if (p < md) return get(p, l, md, id << 1);
  return get(p, md, r, id << 1 | 1);
}
long long getrng(int l, int r, int s = 0, int e = n, int id = 1) {
  if (e <= l || r <= s) return 0;
  if (l <= s && e <= r) return seg[id].sum;
  shift(id);
  int md = (s + e) >> 1;
  return (getrng(l, r, s, md, id << 1) + getrng(l, r, md, e, id << 1 | 1)) %
         mod;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> mod;
  long long tmp = mod, phi = mod;
  for (int i = 2; i * i <= mod; i++) {
    if (tmp % i) continue;
    while (tmp % i == 0) tmp /= i;
    P.push_back(i);
  }
  if (1 < tmp) P.push_back(tmp);
  for (int p : P) phi = phi / p * (p - 1);
  for (int i = 0; i < (int)(P.size()); i++) {
    pw[i][0] = 1;
    for (int j = 1; j < 20 * N; j++) pw[i][j] = pw[i][j - 1] * P[i] % mod;
  }
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    fac(x, A);
    modify(i);
  }
  int q;
  cin >> q;
  while (q--) {
    int typ;
    cin >> typ;
    if (typ == 1) {
      int x, l, r;
      cin >> l >> r >> x;
      fac(x, A);
      upd(l - 1, r);
    } else if (typ == 2) {
      int p, x;
      cin >> p >> x;
      p--;
      A = get(p);
      fac(x, B);
      A.x = A.x * Pow(B.x, phi - 1) % mod;
      for (int i = 0; i < 10; i++) A.cnt[i] -= B.cnt[i];
      A.y = A.x;
      for (int i = 0; i < (int)(P.size()); i++)
        A.y = A.y * pw[i][A.cnt[i]] % mod;
      modify(p);
    } else {
      int l, r;
      cin >> l >> r;
      cout << getrng(l - 1, r) << '\n';
    }
  }
  return 0;
}
