#include <bits/stdc++.h>
template <typename T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool flag = false;
  while (!isdigit(c)) {
    if (c == '-') flag = true;
    c = getchar();
  }
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  if (flag) x = -x;
}
using namespace std;
int n, P, q;
inline long long quickpow(long long x, int k) {
  long long res = 1;
  while (k) {
    if (k & 1) res = res * x % P;
    x = x * x % P;
    k >>= 1;
  }
  return res;
}
int a[101000];
int pri[101000], ptot, phi;
inline void Divi(int x) {
  phi = 1;
  for (int i = 2; i * i <= x; ++i) {
    if (x % i == 0) {
      pri[++ptot] = i;
      phi *= (i - 1);
      x /= i;
      while (x % i == 0) x /= i, phi *= i;
    }
  }
  if (x > 1) pri[++ptot] = x, phi *= (x - 1);
}
int ls[401000], rs[401000], root, ttot;
struct node {
  int h[10];
  node() { memset(h, 0, sizeof(h)); }
  inline void clear() { memset(h, 0, sizeof(h)); }
};
long long sum[401000];
node tag[401000];
long long tagrst[401000], tagmul[401000];
inline void pushup(int cur) { sum[cur] = (sum[ls[cur]] + sum[rs[cur]]) % P; }
void build(int L, int R, int &cur) {
  cur = ++ttot;
  tagrst[cur] = tagmul[cur] = 1;
  if (L == R) {
    sum[cur] = a[L];
    for (int i = 1; i <= ptot; ++i) {
      while (a[L] % pri[i] == 0) ++tag[cur].h[i], a[L] /= pri[i];
    }
    tagrst[cur] = a[L];
    return;
  }
  int mid = (L + R) >> 1;
  build(L, mid, ls[cur]), build(mid + 1, R, rs[cur]);
  pushup(cur);
}
bool havt[401000];
inline void pusht(int cur, node nd, int rst, int mul) {
  for (int i = 1; i <= ptot; ++i) tag[cur].h[i] += nd.h[i];
  tagrst[cur] = tagrst[cur] * rst % P;
  tagmul[cur] = tagmul[cur] * mul % P;
  sum[cur] = sum[cur] * mul % P;
  havt[cur] = true;
}
inline void pushdown(int cur) {
  if (havt[cur])
    pusht(ls[cur], tag[cur], tagrst[cur], tagmul[cur]),
        pusht(rs[cur], tag[cur], tagrst[cur], tagmul[cur]),
        havt[cur] = false, tag[cur].clear(), tagrst[cur] = tagmul[cur] = 1;
}
void modify_mul(int L, int R, int l, int r, node nd, int rst, int mul,
                int cur) {
  if (l <= L && R <= r) return pusht(cur, nd, rst, mul), void();
  int mid = (L + R) >> 1;
  pushdown(cur);
  if (l <= mid) modify_mul(L, mid, l, r, nd, rst, mul, ls[cur]);
  if (r > mid) modify_mul(mid + 1, R, l, r, nd, rst, mul, rs[cur]);
  pushup(cur);
}
void modify_div(int L, int R, int pos, int x, int cur) {
  if (L == R) {
    for (int i = 1; i <= ptot; ++i)
      while (x % pri[i] == 0) x /= pri[i], --tag[cur].h[i];
    sum[cur] = tagrst[cur] = tagrst[cur] * quickpow(x, phi - 1) % P;
    for (int i = 1; i <= ptot; ++i)
      sum[cur] = sum[cur] * quickpow(pri[i], tag[cur].h[i]) % P;
    return;
  }
  int mid = (L + R) >> 1;
  pushdown(cur);
  if (pos <= mid)
    modify_div(L, mid, pos, x, ls[cur]);
  else
    modify_div(mid + 1, R, pos, x, rs[cur]);
  pushup(cur);
}
long long query(int L, int R, int l, int r, int cur) {
  if (l <= L && R <= r) return sum[cur];
  int mid = (L + R) >> 1;
  long long res = 0;
  pushdown(cur);
  if (l <= mid) res += query(L, mid, l, r, ls[cur]);
  if (r > mid) res += query(mid + 1, R, l, r, rs[cur]);
  return res % P;
}
int main() {
  read(n), read(P);
  Divi(P);
  for (int i = 1; i <= n; ++i) read(a[i]);
  build(1, n, root);
  read(q);
  while (q--) {
    int op;
    read(op);
    if (op == 1) {
      int l, r, x;
      read(l), read(r), read(x);
      int tmpx = x;
      node nd;
      for (int i = 1; i <= ptot; ++i)
        while (x % pri[i] == 0) ++nd.h[i], x /= pri[i];
      modify_mul(1, n, l, r, nd, x, tmpx, root);
    } else if (op == 2) {
      int p, x;
      read(p), read(x);
      modify_div(1, n, p, x, root);
    } else {
      int l, r;
      read(l), read(r);
      long long res = query(1, n, l, r, root);
      printf("%lld\n", (res % P + P) % P);
    }
  }
  return 0;
}
