#include <bits/stdc++.h>
using namespace std;
const int maxi = 1e5 + 10;
const int block = 222;
int mo;
vector<pair<int, int>> v[maxi];
int n;
int order[maxi], mp[maxi];
int sumBlock[maxi], blockB[maxi], blockC[maxi];
int b[maxi], c[maxi], d[maxi], a[maxi];
int blockSpec[20][maxi];
int arraySpec[20][maxi];
int fi;
int modulPrimes;
int read_int() {
  char r;
  bool start = false, neg = false;
  int ret = 0;
  while (true) {
    r = getchar();
    if ((r - '0' < 0 || r - '0' > 9) && r != '-' && !start) {
      continue;
    }
    if ((r - '0' < 0 || r - '0' > 9) && r != '-' && start) {
      break;
    }
    if (start) ret *= 10;
    start = true;
    if (r == '-')
      neg = true;
    else
      ret += r - '0';
  }
  if (!neg)
    return ret;
  else
    return -ret;
}
int step(int x, int y) {
  if (!y) return 1;
  int p = step(x, y / 2);
  if (y & 1) return ((1ll * p * p) % mo * x) % mo;
  return 1ll * p * p % mo;
}
int normalStep(int x, int y) {
  if (!y) return 1;
  int p = normalStep(x, y / 2);
  if (y & 1) return p * p * x;
  return p * p;
}
int gcd(int x, int mo) {
  int gcdValue = 1;
  for (int i = 1; i <= modulPrimes; i++) {
    while (x % mp[i] == 0) {
      x /= mp[i];
      gcdValue *= mp[i];
    }
  }
  return gcdValue;
}
void addCoprime(int l, int r, int mulValue) {
  for (int i = l; i <= r; i++) {
    int curBlock = i / block;
    c[i] = (1ll * c[i] * mulValue) % mo;
    sumBlock[curBlock] -= d[i];
    d[i] = (1ll * b[i] * c[i]) % mo;
    sumBlock[curBlock] += d[i];
    if (sumBlock[curBlock] < 0) sumBlock[curBlock] += mo;
    if (sumBlock[curBlock] >= mo) sumBlock[curBlock] -= mo;
  }
}
void mulCoprime(int l, int r, int mulValue) {
  if (r - l <= 2 * block) {
    addCoprime(l, r, mulValue);
    return;
  }
  int startBlock = l / block;
  int endBlock = r / block;
  for (int i = startBlock + 1; i < endBlock; i++)
    blockC[i] = (1ll * mulValue * blockC[i]) % mo;
  addCoprime(l, (startBlock + 1) * block - 1, mulValue);
  addCoprime(endBlock * block, r, mulValue);
}
void addFactor(int l, int r, int mulValue) {
  for (int i = l; i <= r; i++) {
    int curBlock = i / block;
    b[i] = (1ll * b[i] * mulValue) % mo;
    for (auto j : v[mulValue]) arraySpec[order[j.first]][i] += j.second;
    sumBlock[curBlock] -= d[i];
    d[i] = (1ll * b[i] * c[i]) % mo;
    sumBlock[curBlock] += d[i];
    if (sumBlock[curBlock] < 0) sumBlock[curBlock] += mo;
    if (sumBlock[curBlock] >= mo) sumBlock[curBlock] -= mo;
  }
}
void mulOneFactor(int l, int r, int mulValue) {
  if (r - l <= 2 * block) {
    addFactor(l, r, mulValue);
    return;
  }
  int startBlock = l / block;
  int endBlock = r / block;
  for (int i = startBlock + 1; i < endBlock; i++) {
    blockB[i] = (1ll * blockB[i] * mulValue) % mo;
    for (auto j : v[mulValue]) blockSpec[order[j.first]][i] += j.second;
  }
  addFactor(l, (startBlock + 1) * block - 1, mulValue);
  addFactor(endBlock * block, r, mulValue);
  return;
}
void mulFactors(int l, int r, int nzd) { mulOneFactor(l, r, nzd); }
void mul(int l, int r, int x) {
  int nzd = gcd(x, mo);
  mulCoprime(l, r, x / nzd);
  mulFactors(l, r, nzd);
}
int sumInterval(int l, int r) {
  int sum = 0;
  for (int i = l; i <= r; i++)
    sum =
        (sum + (1ll * d[i] * blockC[i / block]) % mo * blockB[i / block]) % mo;
  return sum;
}
int sum(int l, int r) {
  if (r - l <= 2 * block) return sumInterval(l, r);
  int startBlock = l / block;
  int endBlcok = r / block;
  int ans = 0;
  for (int i = startBlock + 1; i < endBlcok; i++)
    ans = (ans + (1ll * blockC[i] * sumBlock[i]) % mo * blockB[i]) % mo;
  ans = (ans + sumInterval(l, (startBlock + 1) * block - 1)) % mo;
  ans += sumInterval(endBlcok * block, r);
  return ans % mo;
}
void divCoprime(int poz, int x) {
  int mulValue = step(x, fi - 1);
  int curBlock = poz / block;
  c[poz] = (1ll * c[poz] * mulValue) % mo;
  sumBlock[curBlock] -= d[poz];
  d[poz] = (1ll * c[poz] * b[poz]) % mo;
  sumBlock[curBlock] += d[poz];
  if (sumBlock[curBlock] < 0) sumBlock[curBlock] += mo;
  if (sumBlock[curBlock] >= mo) sumBlock[curBlock] -= mo;
}
void divideBlock(int x, int divideValue) {
  for (auto i : v[divideValue]) {
    int factorId = order[i.first];
    blockSpec[factorId][x] -= i.second;
  }
  blockB[x] = 1;
  for (int i = 1; i <= modulPrimes; i++)
    blockB[x] = (1ll * blockB[x] * step(mp[i], blockSpec[i][x])) % mo;
}
void divFactors(int p, int x) {
  int normalDivide = 1;
  for (auto i : v[x]) {
    int factorId = order[i.first];
    normalDivide *= normalStep(i.first, min(i.second, arraySpec[factorId][p]));
  }
  int currentBlock = p / block;
  int mulValue = x / normalDivide;
  mul(currentBlock * block, min(n, (currentBlock + 1) * block - 1), mulValue);
  divideBlock(currentBlock, mulValue);
  for (auto i : v[x]) {
    int factorId = order[i.first];
    arraySpec[factorId][p] -= i.second;
  }
  b[p] = 1;
  for (int i = 1; i <= modulPrimes; i++)
    b[p] = (1ll * b[p] * step(mp[i], arraySpec[i][p])) % mo;
  sumBlock[currentBlock] -= d[p];
  d[p] = (1ll * c[p] * b[p]) % mo;
  sumBlock[currentBlock] += d[p];
  if (sumBlock[currentBlock] < 0) sumBlock[currentBlock] += mo;
  if (sumBlock[currentBlock] >= mo) sumBlock[currentBlock] -= mo;
}
void divs(int p, int x) {
  int nzd = gcd(x, mo);
  divCoprime(p, x / nzd);
  divFactors(p, nzd);
}
void factorization() {
  for (int i = 2; i < maxi; i++)
    if (v[i].size() == 0) {
      v[i].push_back({i, 1});
      for (int j = 2 * i; j < maxi; j += i) {
        int m = j;
        int cnt = 0;
        while (m % i == 0) {
          cnt++;
          m /= i;
        }
        v[j].push_back({i, cnt});
      }
    }
}
void calculate_phi() {
  int m = mo;
  double x = mo;
  for (int i = 2; i * i <= m; i++)
    if (m % i == 0) {
      while (m % i == 0) m /= i;
      x *= (1 - 1.00 / i);
      order[i] = ++modulPrimes;
      mp[modulPrimes] = i;
    }
  if (m > 1) x *= (1 - 1.00 / m);
  if (m > 1 && m <= 100000) {
    order[m] = ++modulPrimes;
    mp[modulPrimes] = m;
  }
  fi = round(x);
}
void prepare_everything() {
  for (int i = 0; i < maxi; i++) {
    blockB[i] = 1;
    blockC[i] = 1;
  }
  for (int i = 1; i <= n; i++) {
    long long x = gcd(a[i], mo);
    b[i] = x % mo;
    c[i] = (a[i] / x) % mo;
    d[i] = a[i] % mo;
    sumBlock[i / block] = (sumBlock[i / block] + a[i]) % mo;
    for (auto j : v[x]) {
      int factorId = order[j.first];
      arraySpec[factorId][i] = j.second;
    }
  }
}
int main() {
  cin >> n >> mo;
  for (int i = 1; i <= n; i++) a[i] = read_int();
  factorization();
  calculate_phi();
  prepare_everything();
  int q;
  cin >> q;
  while (q--) {
    int tip;
    scanf("%d", &tip);
    if (tip == 1) {
      int l, r, x;
      l = read_int();
      r = read_int();
      x = read_int();
      mul(l, r, x);
    }
    if (tip == 2) {
      int p, x;
      p = read_int();
      x = read_int();
      divs(p, x);
    }
    if (tip == 3) {
      int l, r;
      l = read_int();
      r = read_int();
      int ans = sum(l, r);
      printf("%d\n", ans);
    }
  }
  return 0;
}
