#include <bits/stdc++.h>
using namespace std;
const int lim = 17 * 100001;
int mod, v[100010], arb[400010], lazy[400010], fi, vaz[100010], put[10],
    lazy1[400010][9], prec[9][lim + 1], l1;
char leaf[400010];
vector<int> primes;
int rid_put(int a, int b) {
  int sol = 1;
  for (int i = 1; i <= b; i <<= 1) {
    if (b & i) sol = (1LL * sol * a) % mod;
    a = (1LL * a * a) % mod;
  }
  return sol;
}
int vl(int nod) {
  if (leaf[nod] == 0) return arb[nod];
  int p = 1;
  for (int i = 0; i < l1; i++) p = (1LL * p * prec[i][lazy1[nod][i]]) % mod;
  return (1LL * arb[nod] * p) % mod;
}
void init(int nod, int st, int dr) {
  lazy[nod] = 1;
  if (st == dr) {
    int val1 = 1, x = v[st];
    for (int j = 2; j * j <= x; j++)
      if (x % j == 0) {
        int p = 0, c = 1;
        while (x % j == 0) {
          x /= j;
          c *= j;
          p++;
        }
        if (mod % j != 0)
          val1 *= c;
        else
          lazy1[nod][vaz[j]] = p;
      }
    if (x > 1) {
      if (mod % x != 0)
        val1 *= x;
      else
        lazy1[nod][vaz[x]] = 1;
    }
    arb[nod] = val1;
    leaf[nod] = 1;
    return;
  }
  int mid = (st + dr) / 2;
  init(nod * 2, st, mid);
  init(nod * 2 + 1, mid + 1, dr);
  arb[nod] = (vl(nod * 2) + vl(nod * 2 + 1)) % mod;
}
void propag(int nod, int st, int dr) {
  arb[nod] = (1LL * arb[nod] * lazy[nod]) % mod;
  if (st < dr) {
    lazy[nod * 2] = (1LL * lazy[nod * 2] * lazy[nod]) % mod;
    lazy[nod * 2 + 1] = (1LL * lazy[nod * 2 + 1] * lazy[nod]) % mod;
    int p = 1;
    for (int i = 0; i < l1; i++) {
      lazy1[nod * 2][i] += lazy1[nod][i];
      lazy1[nod * 2 + 1][i] += lazy1[nod][i];
      p = (1LL * p * prec[i][lazy1[nod][i]]) % mod;
      lazy1[nod][i] = 0;
    }
    arb[nod] = (1LL * arb[nod] * p) % mod;
  }
  lazy[nod] = 1;
}
void update(int nod, int st, int dr, int left, int right, int x) {
  if (left <= st && dr <= right) {
    lazy[nod] = (1LL * lazy[nod] * x) % mod;
    for (int i = 0; i < 9; i++) lazy1[nod][i] += put[i];
    propag(nod, st, dr);
    return;
  }
  propag(nod, st, dr);
  int mid = (st + dr) / 2;
  if (left <= mid)
    update(nod * 2, st, mid, left, right, x);
  else
    propag(nod * 2, st, mid);
  if (mid < right)
    update(nod * 2 + 1, mid + 1, dr, left, right, x);
  else
    propag(nod * 2 + 1, mid + 1, dr);
  arb[nod] = (vl(nod * 2) + vl(nod * 2 + 1)) % mod;
}
void update1(int nod, int st, int dr, int poz, int x) {
  propag(nod, st, dr);
  if (st == dr) {
    arb[nod] = (1LL * arb[nod] * rid_put(x, fi - 1)) % mod;
    for (int i = 0; i < 9; i++) lazy1[nod][i] -= put[i];
    return;
  }
  int mid = (st + dr) / 2;
  if (poz <= mid) {
    update1(nod * 2, st, mid, poz, x);
    propag(nod * 2 + 1, mid + 1, dr);
  } else {
    update1(nod * 2 + 1, mid + 1, dr, poz, x);
    propag(nod * 2, st, mid);
  }
  arb[nod] = (vl(nod * 2) + vl(nod * 2 + 1)) % mod;
}
int query(int nod, int st, int dr, int left, int right) {
  propag(nod, st, dr);
  if (left <= st && dr <= right) return vl(nod);
  int mid = (st + dr) / 2;
  int rez = 0;
  if (left <= mid) rez = (rez + query(nod * 2, st, mid, left, right)) % mod;
  if (mid < right)
    rez = (rez + query(nod * 2 + 1, mid + 1, dr, left, right)) % mod;
  return rez;
}
int main() {
  int n, l, r, x, q, tip;
  scanf("%d%d", &n, &mod);
  for (int i = 1; i <= n; i++) scanf("%d", &v[i]);
  int nr = mod;
  fi = mod;
  for (int i = 2; 1LL * i * i <= nr; i++)
    if (nr % i == 0) {
      while (nr % i == 0) nr /= i;
      fi = (fi / i) * (i - 1);
    }
  if (nr > 1) fi = (fi / nr) * (nr - 1);
  int a = mod, lim1 = 1e5;
  for (int i = 2; i <= lim1; i++)
    if (a % i == 0) {
      while (a % i == 0) a /= i;
      primes.push_back(i);
      vaz[i] = primes.size() - 1;
    }
  l1 = primes.size();
  for (int i = 0; i < primes.size(); i++) {
    int p = 1;
    for (int j = 0; j <= lim; j++) {
      prec[i][j] = p;
      p = (1LL * p * primes[i]) % mod;
    }
  }
  init(1, 1, n);
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    scanf("%d", &tip);
    if (tip == 1) {
      scanf("%d%d%d", &l, &r, &x);
      for (int j = 0; j < 9; j++) put[j] = 0;
      int val1 = 1;
      for (int j = 2; j * j <= x; j++)
        if (x % j == 0) {
          int p = 0, c = 1;
          while (x % j == 0) {
            x /= j;
            c *= j;
            p++;
          }
          if (mod % j != 0)
            val1 *= c;
          else
            put[vaz[j]] = p;
        }
      if (x > 1) {
        if (mod % x != 0)
          val1 *= x;
        else
          put[vaz[x]] = 1;
      }
      update(1, 1, n, l, r, val1);
    } else if (tip == 2) {
      scanf("%d%d", &l, &x);
      for (int j = 0; j < 9; j++) put[j] = 0;
      int val1 = 1;
      for (int j = 2; j * j <= x; j++)
        if (x % j == 0) {
          int p = 0, c = 1;
          while (x % j == 0) {
            x /= j;
            c *= j;
            p++;
          }
          if (mod % j != 0)
            val1 *= c;
          else
            put[vaz[j]] = p;
        }
      if (x > 1) {
        if (mod % x != 0)
          val1 *= x;
        else
          put[vaz[x]] = 1;
      }
      update1(1, 1, n, l, val1);
    } else {
      scanf("%d%d", &l, &r);
      printf("%d\n", query(1, 1, n, l, r));
    }
  }
  return 0;
}
