#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
int mod, phi;
int ksm(long long a, int b, int c = 1) {
  for (; b; b /= 2, a = a * a % mod)
    if (b & 1) c = c * a % mod;
  return c;
}
vector<int> pr;
int factor(int x) {
  int t = x;
  for (int i = 2; i * i <= x; ++i)
    if (x % i == 0)
      for (pr.push_back(i); x % i == 0; x /= i)
        ;
  if (x > 1) pr.push_back(x);
  for (int i : pr) t = t / i * (i - 1);
  return t;
}
struct mod_int {
  int val, a[20];
  mod_int() {
    val = 1;
    memset(a, 0, sizeof a);
  }
  mod_int(int x) {
    for (int i = 0; i < (int)pr.size(); ++i)
      for (a[i] = 0; x % pr[i] == 0; x /= pr[i]) ++a[i];
    val = x % mod;
  }
  void operator*=(const mod_int& t) {
    val = (long long)val * t.val % mod;
    for (int i = 0; i < (int)pr.size(); ++i) a[i] += t.a[i];
  }
  void operator/=(const mod_int& t) {
    val = ksm(t.val, phi - 1, val);
    for (int i = 0; i < (int)pr.size(); ++i) a[i] -= t.a[i];
  }
  operator int() {
    int ret = val;
    for (int i = 0; i < (int)pr.size(); ++i) ret = ksm(pr[i], a[i], ret);
    return ret;
  }
} mod_tag[N * 4];
int tag[N * 4], sum[N * 4];
void pd(int o) {
  if (tag[o] != 1) {
    tag[o * 2] = (long long)tag[o * 2] * tag[o] % mod;
    tag[o * 2 + 1] = (long long)tag[o * 2 + 1] * tag[o] % mod;
    sum[o * 2] = (long long)sum[o * 2] * tag[o] % mod;
    sum[o * 2 + 1] = (long long)sum[o * 2 + 1] * tag[o] % mod;
    mod_tag[o * 2] *= mod_tag[o];
    mod_tag[o * 2 + 1] *= mod_tag[o];
    tag[o] = 1;
    mod_tag[o] = mod_int();
  }
}
int a[N];
void bt(int o, int l, int r) {
  if (l == r) {
    mod_tag[o] = mod_int(a[l]);
    tag[o] = sum[o] = a[l];
    return;
  }
  int mid = (l + r) / 2;
  tag[o] = 1;
  mod_tag[o] = mod_int();
  bt(o * 2, l, mid);
  bt(o * 2 + 1, mid + 1, r);
  sum[o] = (sum[o * 2] + sum[o * 2 + 1]) % mod;
}
int q1, q2, q3;
mod_int q4;
void modify1(int o, int l, int r) {
  if (q1 <= l && r <= q2) {
    tag[o] = (long long)tag[o] * q3 % mod;
    sum[o] = (long long)sum[o] * q3 % mod;
    mod_tag[o] *= q4;
    return;
  }
  int mid = (l + r) / 2;
  pd(o);
  if (q1 <= mid) modify1(o * 2, l, mid);
  if (q2 > mid) modify1(o * 2 + 1, mid + 1, r);
  sum[o] = (sum[o * 2] + sum[o * 2 + 1]) % mod;
}
void modify2(int o, int l, int r) {
  if (l == r) {
    mod_tag[o] /= q4;
    tag[o] = sum[o] = mod_tag[o];
    return;
  }
  int mid = (l + r) / 2;
  pd(o);
  if (q1 <= mid)
    modify2(o * 2, l, mid);
  else
    modify2(o * 2 + 1, mid + 1, r);
  sum[o] = (sum[o * 2] + sum[o * 2 + 1]) % mod;
}
void query(int o, int l, int r) {
  if (q1 <= l && r <= q2) {
    q3 = (q3 + sum[o]) % mod;
    return;
  }
  int mid = (l + r) / 2;
  pd(o);
  if (q1 <= mid) query(o * 2, l, mid);
  if (q2 > mid) query(o * 2 + 1, mid + 1, r);
}
int n, q;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> mod;
  phi = factor(mod);
  for (int i = 1; i <= n; ++i) cin >> a[i];
  bt(1, 1, n);
  for (cin >> q; q-- > 0;) {
    int op;
    cin >> op;
    if (op == 1) {
      cin >> q1 >> q2 >> q3;
      q4 = mod_int(q3);
      modify1(1, 1, n);
    } else if (op == 2) {
      cin >> q1 >> q3;
      q4 = mod_int(q3);
      modify2(1, 1, n);
    } else {
      cin >> q1 >> q2;
      q3 = 0;
      query(1, 1, n);
      cout << q3 << '\n';
    }
  }
  return 0;
}
