#include <bits/stdc++.h>
using namespace std;
template <typename T>
void maxtt(T &t1, T t2) {
  t1 = max(t1, t2);
}
template <typename T>
void mintt(T &t1, T t2) {
  t1 = min(t1, t2);
}
bool debug = 0;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
string direc = "URDL";
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "YES" : "NO");
  exit(0);
}
void addmod(int &x, int y, int mod = 1000000007) {
  assert(y >= 0);
  x += y;
  if (x >= mod) x -= mod;
  assert(x >= 0 && x < mod);
}
void et(int x = -1) {
  printf("%d\n", x);
  exit(0);
}
long long fastPow(long long x, long long y, int mod = 1000000007) {
  long long ans = 1;
  while (y > 0) {
    if (y & 1) ans = (x * ans) % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
long long gcd1(long long x, long long y) { return y ? gcd1(y, x % y) : x; }
int mod, N;
vector<pair<int, int> > psm;
int T[100035 * 4], ts[100035 * 4][10], lz[100035 * 4], lzs[100035 * 4][10];
int a[100035], X, xs[13];
int prepw[10][2000000];
void Up(int rt, int l, int r) {
  T[rt] = (T[(rt << 1)] + T[(rt << 1 | 1)]) % mod;
}
void build(int rt, int l, int r) {
  if (l + 1 == r) {
    int x = a[r];
    for (int(i) = 0; (i) < (int)(N); (i)++) {
      while (x % psm[i].first == 0) {
        x /= psm[i].first;
        ts[rt][i]++;
      }
    }
    T[rt] = a[r] % mod;
    lz[rt] = x;
    return;
  }
  int mid = (l + r) / 2;
  build((rt << 1), l, mid);
  build((rt << 1 | 1), mid, r);
  Up(rt, l, r);
}
void Down(int rt, int l, int r) {
  if (l + 1 == r) return;
  if (lz[rt] != 1) {
    T[(rt << 1)] = (long long)T[(rt << 1)] * lz[rt] % mod;
    lz[(rt << 1)] = (long long)lz[(rt << 1)] * lz[rt] % mod;
    T[(rt << 1 | 1)] = (long long)T[(rt << 1 | 1)] * lz[rt] % mod;
    lz[(rt << 1 | 1)] = (long long)lz[(rt << 1 | 1)] * lz[rt] % mod;
    lz[rt] = 1;
  }
  for (int(j) = 0; (j) < (int)(N); (j)++)
    if (lzs[rt][j] != 0) {
      ts[(rt << 1)][j] += lzs[rt][j];
      lzs[(rt << 1)][j] += lzs[rt][j];
      ts[(rt << 1 | 1)][j] += lzs[rt][j];
      lzs[(rt << 1 | 1)][j] += lzs[rt][j];
      T[(rt << 1)] = (long long)T[(rt << 1)] * prepw[j][lzs[rt][j]] % mod;
      T[(rt << 1 | 1)] =
          (long long)T[(rt << 1 | 1)] * prepw[j][lzs[rt][j]] % mod;
      lzs[rt][j] = 0;
    }
}
void upt(int rt, int l, int r, int L, int R, int px) {
  if (R <= l || r <= L) return;
  if (L <= l && r <= R) {
    T[rt] = (long long)T[rt] * px % mod;
    lz[rt] = (long long)lz[rt] * X % mod;
    for (int(j) = 0; (j) < (int)(N); (j)++) {
      ts[rt][j] += xs[j];
      lzs[rt][j] += xs[j];
    }
    return;
  }
  Down(rt, l, r);
  int mid = (l + r) / 2;
  upt((rt << 1), l, mid, L, R, px);
  upt((rt << 1 | 1), mid, r, L, R, px);
  Up(rt, l, r);
}
long long extend_gcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1, y = 0;
    return a;
  } else {
    long long r = extend_gcd(b, a % b, y, x);
    y -= x * (a / b);
    return r;
  }
}
long long inv(long long a, long long n) {
  long long x, y;
  extend_gcd(a, n, x, y);
  x = (x % n + n) % n;
  return x;
}
void uptS(int rt, int l, int r, int p) {
  if (l + 1 == r) {
    lz[rt] = (long long)lz[rt] * inv(X, mod) % mod;
    T[rt] = lz[rt];
    for (int(j) = 0; (j) < (int)(N); (j)++) {
      ts[rt][j] -= xs[j];
      T[rt] = (long long)T[rt] * prepw[j][ts[rt][j]] % mod;
    }
    return;
  }
  Down(rt, l, r);
  int mid = (l + r) / 2;
  if (p <= mid)
    uptS((rt << 1), l, mid, p);
  else
    uptS((rt << 1 | 1), mid, r, p);
  Up(rt, l, r);
}
int qy(int rt, int l, int r, int L, int R) {
  if (R <= l || r <= L) return 0;
  if (L <= l && r <= R) {
    return T[rt];
  }
  Down(rt, l, r);
  int mid = (l + r) / 2;
  return (qy((rt << 1), l, mid, L, R) + qy((rt << 1 | 1), mid, r, L, R)) % mod;
}
void fmain(int tid) {
  scanf("%d%d", &n, &mod);
  int x = mod;
  for (int i = 2; (long long)i * i <= x; i++)
    if (x % i == 0) {
      int c = 0;
      while (x % i == 0) {
        x /= i;
        c++;
      }
      psm.push_back({i, c});
    }
  if (x > 1) psm.push_back({x, 1});
  N = psm.size();
  for (int(i) = 1; (i) <= (int)(n); (i)++) scanf("%d", a + i);
  for (int(i) = 0; (i) < (int)(100035 * 4); (i)++) lz[i] = 1;
  build(1, 0, n);
  for (int(j) = 0; (j) < (int)(N); (j)++) {
    prepw[j][0] = 1;
    for (int(i) = 1; (i) <= (int)(2000000 - 1); (i)++)
      prepw[j][i] = (long long)prepw[j][i - 1] * psm[j].first % mod;
  }
  scanf("%d", &m);
  for (int(i) = 1; (i) <= (int)(m); (i)++) {
    int t, l, r;
    scanf("%d", &t);
    if (t == 1) {
      scanf("%d%d%d", &l, &r, &X);
      int x = X;
      for (int(j) = 0; (j) < (int)(N); (j)++) {
        xs[j] = 0;
        while (X % psm[j].first == 0) {
          X /= psm[j].first;
          xs[j]++;
        }
      }
      upt(1, 0, n, l - 1, r, x);
    } else if (t == 2) {
      scanf("%d%d", &l, &X);
      for (int(j) = 0; (j) < (int)(N); (j)++) {
        xs[j] = 0;
        while (X % psm[j].first == 0) {
          X /= psm[j].first;
          xs[j]++;
        }
      }
      uptS(1, 0, n, l);
    } else {
      scanf("%d%d", &l, &r);
      int z = qy(1, 0, n, l - 1, r);
      printf("%d\n", z);
    }
  }
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain(i);
  }
  return 0;
}
