#include <bits/stdc++.h>
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
using namespace ::std;
const int maxn = 1e5 + 500;
struct num {
  int v[9], baghi, sum, zarib;
};
vector<int> amel;
int mod, phi;
num Glob;
num seg[maxn * 4];
int poww(long long a, int b) {
  long long ans = 1;
  while (b) {
    if (b & 1) {
      ans = (ans * a) % mod;
    }
    b >>= 1;
    a = (a * a) % mod;
  }
  return ans;
}
inline void add(num &a, const num &b) {
  for (int i = 0; i < amel.size(); i++) {
    a.v[i] += b.v[i];
  }
  a.baghi = ((long long)b.baghi * a.baghi) % mod;
  a.sum = ((long long)a.sum * b.zarib) % mod;
  a.zarib = ((long long)a.zarib * b.zarib) % mod;
}
inline void kamKon(num &a, const num &b) {
  for (int i = 0; i < amel.size(); i++) {
    a.v[i] -= b.v[i];
  }
  a.baghi = ((long long)a.baghi * b.baghi) % mod;
  a.zarib = a.baghi;
  for (int i = 0; i < amel.size(); i++) {
    a.zarib = ((long long)a.zarib * poww(amel[i], a.v[i])) % mod;
  }
  a.sum = a.zarib;
}
inline void shift(int node) {
  add(seg[2 * node], seg[node]);
  add(seg[2 * node + 1], seg[node]);
  fill(seg[node].v, seg[node].v + amel.size(), 0);
  seg[node].baghi = 1;
  seg[node].zarib = 1;
}
inline void merg(num &a, num &b, num &c) { a.sum = (b.sum + c.sum) % mod; }
void updateTagh(int L, int R, int node, int p) {
  if (L + 1 == R) {
    kamKon(seg[node], Glob);
    return;
  }
  int mid = (L + R) / 2;
  shift(node);
  if (p < mid)
    updateTagh(L, mid, 2 * node, p);
  else
    updateTagh(mid, R, 2 * node + 1, p);
  merg(seg[node], seg[2 * node], seg[2 * node + 1]);
}
void update(int L, int R, int node, int l, int r) {
  if (l <= L && R <= r) {
    add(seg[node], Glob);
    return;
  }
  if (R <= l || r <= L) {
    return;
  }
  int mid = (L + R) / 2;
  shift(node);
  update(L, mid, 2 * node, l, r);
  update(mid, R, 2 * node + 1, l, r);
  merg(seg[node], seg[2 * node], seg[2 * node + 1]);
}
int findSum(int L, int R, int node, int l, int r) {
  if (l <= L && R <= r) {
    return seg[node].sum;
  }
  if (R <= l || r <= L) {
    return 0;
  }
  int mid = (L + R) / 2;
  return (((long long)((findSum(L, mid, 2 * node, l, r) +
                        findSum(mid, R, 2 * node + 1, l, r)) %
                       mod)) *
          seg[node].zarib) %
         mod;
}
void bild(int l, int r, int node) {
  seg[node].baghi = 1;
  seg[node].zarib = 1;
  seg[node].sum = r - l;
  if (l + 1 == r) return;
  int mid = (l + r) / 2;
  bild(l, mid, 2 * node);
  bild(mid, r, 2 * node + 1);
}
num tajzie(int a) {
  num e;
  e.zarib = a;
  e.sum = a;
  for (int i = 0; i < amel.size(); i++) {
    int cnt = 0;
    while (a % amel[i] == 0) {
      cnt++;
      a /= amel[i];
    }
    e.v[i] = cnt;
  }
  e.baghi = a;
  return e;
}
void makeAmel(int mod) {
  for (int i = 2; i * i <= mod; i++) {
    if (mod % i == 0) {
      amel.push_back(i);
      while (mod % i == 0) mod /= i;
    }
  }
  if (mod > 1) {
    amel.push_back(mod);
  }
}
int calculatephi(int mod) {
  int ans = 1;
  num e = tajzie(mod);
  for (int i = 0; i < amel.size(); i++) {
    ans *= (amel[i] - 1) * poww(amel[i], e.v[i] - 1);
  }
  return ans;
}
int main() {
  int n, q;
  cin >> n >> mod;
  makeAmel(mod);
  phi = calculatephi(mod);
  bild(0, n, 1);
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    Glob = tajzie(a);
    update(0, n, 1, i, i + 1);
  }
  cin >> q;
  for (int i = 0; i < q; i++) {
    int typ;
    cin >> typ;
    if (typ == 1) {
      int l, r, x;
      cin >> l >> r >> x;
      l--;
      r--;
      Glob = tajzie(x);
      update(0, n, 1, l, r + 1);
    }
    if (typ == 2) {
      int p, x;
      cin >> p >> x;
      p--;
      Glob = tajzie(x);
      Glob.baghi = poww(Glob.baghi, phi - 1);
      updateTagh(0, n, 1, p);
    }
    if (typ == 3) {
      int l, r;
      cin >> l >> r;
      l--;
      r--;
      cout << findSum(0, n, 1, l, r + 1) << endl;
    }
  }
}
