#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long INFF = 0x3f3f3f3f3f3f3f3fll;
const long long M = 1e9 + 7;
const long long maxn = 1e5 + 107;
const double pi = acos(-1.0);
const double eps = 0.0000000001;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
template <typename T>
inline void pr2(T x, int k = 64) {
  long long i;
  for (i = 0; i < k; i++) fprintf(stderr, "%d", (x >> i) & 1);
  putchar(' ');
}
template <typename T>
inline void add_(T &A, int B, long long MOD) {
  A += B;
  (A >= MOD) && (A -= MOD);
}
template <typename T>
inline void mul_(T &A, long long B, long long MOD) {
  A = (A * B) % MOD;
}
template <typename T>
inline void mod_(T &A, long long MOD = M) {
  A %= MOD;
  A += MOD;
  A %= MOD;
}
template <typename T>
inline void max_(T &A, T B) {
  (A < B) && (A = B);
}
template <typename T>
inline void min_(T &A, T B) {
  (A > B) && (A = B);
}
template <typename T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
template <typename T>
inline T powMM(T a, T b) {
  T ret = 1;
  for (; b; b >>= 1ll, a = (long long)a * a % M)
    if (b & 1) ret = (long long)ret * a % M;
  return ret;
}
int startTime;
void startTimer() { startTime = clock(); }
void printTimer() {
  fprintf(stderr, "/--- Time: %ld milliseconds ---/\n", clock() - startTime);
}
inline int poww(int a, int b, int p) {
  int ret = 1;
  for (; b; b >>= 1, a = (long long)a * a % p)
    if (b & 1) ret = (long long)ret * a % p;
  return ret;
}
int p[12], tot;
struct node {
  int mx, c[12], mc, sx;
  node() {
    mc = mx = 1;
    sx = 0;
    memset(c, 0, sizeof(c));
  }
} T[maxn * 4];
int mod;
void pushdown(int x) {
  mul_(T[x << 1].mc, T[x].mc, mod);
  mul_(T[x << 1].sx, T[x].mc, mod);
  mul_(T[x << 1 | 1].mc, T[x].mc, mod);
  mul_(T[x << 1 | 1].sx, T[x].mc, mod);
  int i;
  T[x].mc = 1;
  for (i = 0; i < tot; i++) {
    T[x << 1].c[i] += T[x].c[i];
    T[x << 1 | 1].c[i] += T[x].c[i];
    T[x].c[i] = 0;
  }
  mul_(T[x << 1].mx, T[x].mx, mod);
  mul_(T[x << 1].sx, T[x].mx, mod);
  mul_(T[x << 1 | 1].mx, T[x].mx, mod);
  mul_(T[x << 1 | 1].sx, T[x].mx, mod);
  T[x].mx = 1;
}
int op, l, r;
int now[12], mx, mc, mul;
int ans;
void solve(int x, int L, int R) {
  int l = max(L, ::l), r = min(R, ::r);
  if (l <= L && R <= r) {
    if (op == 1 || op == 2) {
      int i;
      mul_(T[x].mx, mx, mod);
      mul_(T[x].mc, mc, mod);
      mul_(T[x].sx, mul, mod);
      for (i = 0; i < tot; i++) T[x].c[i] += now[i];
    } else
      add_(ans, T[x].sx, mod);
    if (L == R) {
      int i;
      T[x].mc = 1;
      for (i = 0; i < tot; i++) mul_(T[x].mc, poww(p[i], T[x].c[i], mod), mod);
      T[x].sx = (long long)T[x].mx * T[x].mc % mod;
    }
    return;
  }
  int mid = (L + R) / 2;
  pushdown(x);
  if (l <= mid) solve(x << 1, L, mid);
  if (mid < r) solve(x << 1 | 1, mid + 1, R);
  T[x].sx = (T[x << 1].sx + T[x << 1 | 1].sx) % mod;
  return;
}
void reset() {
  int i;
  for (i = 0; i < tot; i++) now[i] = 0;
  mul = mx = mc = 1;
}
void setit(int x) {
  int i;
  mul = x;
  for (i = 0; i < tot; i++)
    while (x % p[i] == 0) now[i]++, x /= p[i];
  mx = x;
  mc = mul / mx;
}
int main() {
  int q, i, k, _, n;
  op = 1;
  scanf("%d%d", &n, &mod);
  int pwmod = mod;
  for (k = mod, i = 2; i * i <= k; i++)
    if (k % i == 0) {
      p[tot++] = i;
      while (k % i == 0) k /= i;
    }
  if (k != 1) p[tot++] = k;
  for (i = 0; i < tot; i++) pwmod = pwmod / p[i] * (p[i] - 1);
  pwmod--;
  for (i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    reset();
    setit(x);
    l = r = i;
    solve(1, 1, n);
  }
  scanf("%d", &q);
  for (_ = 1; _ <= q; _++) {
    int x, i;
    scanf("%d", &op);
    reset();
    if (op == 1) {
      scanf("%d%d%d", &l, &r, &x);
      setit(x);
    } else if (op == 2) {
      scanf("%d%d", &l, &x);
      r = l;
      setit(x);
      for (i = 0; i < tot; i++) now[i] = -now[i];
      mx = poww(mx, pwmod, mod);
    } else {
      scanf("%d%d", &l, &r);
      ans = 0;
    }
    solve(1, 1, n);
    if (op == 3) printf("%d\n", ans);
  }
}
