#include <bits/stdc++.h>
using namespace std;
struct Num {
  int a = 1, b = 1, cnt[10] = {0};
};
const int N = 100005;
int n, q, Mod, A[N];
int sum[N * 4];
Num laz[N * 4];
vector<int> P;
inline int Power(int a, int b) {
  int ret = 1;
  for (; b; b >>= 1, a = 1LL * a * a % Mod)
    if (b & 1) ret = 1LL * ret * a % Mod;
  return (ret);
}
inline Num operator*(Num X, Num Y) {
  X.a = 1LL * X.a * Y.a % Mod;
  X.b = 1LL * X.b * Y.b % Mod;
  for (int i = 0; i < (int)P.size(); i++) X.cnt[i] += Y.cnt[i];
  return (X);
}
void Build(int id = 1, int l = 0, int r = n) {
  if (r - l < 2) {
    int val = A[l];
    laz[id].a = val % Mod;
    for (int i = 0; i < (int)P.size(); i++)
      while (val % P[i] == 0) val /= P[i], laz[id].cnt[i]++;
    laz[id].b = val % Mod;
    sum[id] = A[l] % Mod;
    return;
  }
  laz[id].a = laz[id].b = 1;
  memset(laz[id].cnt, 0, sizeof(laz[id].cnt));
  Build((id << 1), l, ((l + r) >> 1));
  Build((id << 1 ^ 1), ((l + r) >> 1), r);
  sum[id] = sum[(id << 1)] + sum[(id << 1 ^ 1)];
  if (sum[id] >= Mod) sum[id] -= Mod;
}
inline void Upd(int id, Num val) {
  sum[id] = 1LL * sum[id] * val.a % Mod;
  laz[id] = laz[id] * val;
}
inline void Shift(int id) {
  Upd((id << 1), laz[id]);
  Upd((id << 1 ^ 1), laz[id]);
  laz[id].a = laz[id].b = 1;
  memset(laz[id].cnt, 0, sizeof(laz[id].cnt));
}
void Mult(int le, int ri, Num val, int id = 1, int l = 0, int r = n) {
  if (ri <= l || r <= le) return;
  if (le <= l && r <= ri) {
    Upd(id, val);
    return;
  }
  Shift(id);
  Mult(le, ri, val, (id << 1), l, ((l + r) >> 1));
  Mult(le, ri, val, (id << 1 ^ 1), ((l + r) >> 1), r);
  sum[id] = sum[(id << 1)] + sum[(id << 1 ^ 1)];
  if (sum[id] >= Mod) sum[id] -= Mod;
}
void Set(int i, Num val, int id = 1, int l = 0, int r = n) {
  if (r - l < 2) {
    laz[id] = val;
    sum[id] = val.a;
    return;
  }
  Shift(id);
  if (i < ((l + r) >> 1))
    Set(i, val, (id << 1), l, ((l + r) >> 1));
  else
    Set(i, val, (id << 1 ^ 1), ((l + r) >> 1), r);
  sum[id] = sum[(id << 1)] + sum[(id << 1 ^ 1)];
  if (sum[id] >= Mod) sum[id] -= Mod;
}
Num GetAt(int i, int id = 1, int l = 0, int r = n) {
  if (r - l < 2) return (laz[id]);
  Shift(id);
  if (i < ((l + r) >> 1)) return (GetAt(i, (id << 1), l, ((l + r) >> 1)));
  return (GetAt(i, (id << 1 ^ 1), ((l + r) >> 1), r));
}
int Get(int le, int ri, int id = 1, int l = 0, int r = n) {
  if (ri <= l || r <= le) return (0);
  if (le <= l && r <= ri) return (sum[id]);
  Shift(id);
  int res = Get(le, ri, (id << 1), l, ((l + r) >> 1));
  res += Get(le, ri, (id << 1 ^ 1), ((l + r) >> 1), r);
  if (res >= Mod) res -= Mod;
  return (res);
}
int main() {
  scanf("%d%d", &n, &Mod);
  for (int i = 0; i < n; i++) scanf("%d", &A[i]);
  int _Mod = Mod;
  for (int i = 2; i * i <= Mod; i++)
    if (_Mod % i == 0) {
      P.push_back(i);
      while (_Mod % i == 0) _Mod /= i;
    }
  if (_Mod > 1) P.push_back(_Mod);
  int phi = Mod;
  for (int p : P) phi = phi / p * (p - 1);
  Build();
  scanf("%d", &q);
  for (; q; q--) {
    int tp, l, r, val;
    scanf("%d%d%d", &tp, &l, &r);
    if (tp == 1) {
      scanf("%d", &val);
      Num X;
      X.a = val % Mod;
      for (int i = 0; i < (int)P.size(); i++)
        while (val % P[i] == 0) val /= P[i], X.cnt[i]++;
      X.b = val % Mod;
      Mult(l - 1, r, X);
    } else if (tp == 2) {
      val = r;
      Num X = GetAt(l - 1);
      for (int i = 0; i < (int)P.size(); i++)
        while (val % P[i] == 0) val /= P[i], X.cnt[i]--;
      X.b = 1LL * X.b * Power(val, phi - 1) % Mod;
      X.a = X.b;
      for (int i = 0; i < (int)P.size(); i++)
        X.a = 1LL * X.a * Power(P[i], X.cnt[i]) % Mod;
      Set(l - 1, X);
    } else
      printf("%d\n", Get(l - 1, r) % Mod);
  }
  return 0;
}
