#include <bits/stdc++.h>
using namespace std;
const int N_MAX = 1e5;
int n, q, phi;
long long mod, val[N_MAX], sum[N_MAX];
vector<long long> p, mod_exp;
pair<long long, vector<int>> f[N_MAX], g[N_MAX];
bool lazy[N_MAX];
vector<vector<long long>> stored_pow;
void factor_mod() {
  int x = mod;
  for (int d = 2; d * d <= x; d++) {
    if (x % d != 0) continue;
    p.push_back(d);
    mod_exp.push_back(1);
    x /= d;
    while (x % d == 0) {
      mod_exp.back()++;
      x /= d;
    }
  }
  if (x > 1) {
    p.push_back(x);
    mod_exp.push_back(1);
  }
  phi = 1;
  for (int i = 0; i < p.size(); i++) {
    phi *= p[i] - 1;
    for (int j = 0; j < mod_exp[i] - 1; j++) phi *= p[i];
  }
  stored_pow.resize(p.size(), vector<long long>(1, 1));
}
void factor(int x, pair<long long, vector<int>>& fac) {
  fac.second.resize(p.size(), 0);
  for (int i = 0; i < p.size(); i++) {
    while (x % p[i] == 0) {
      fac.second[i]++;
      x /= p[i];
    }
  }
  fac.first = x;
}
long long quick_exp(long long x, int k) {
  if (k == 0) return 1;
  long long y = quick_exp(x, k / 2);
  y = y * y % mod;
  return (k % 2 ? y * x % mod : y);
}
long long prime_pow(int i, int e) {
  for (int j = stored_pow[i].size(); j <= e; j++)
    stored_pow[i].push_back(stored_pow[i].back() * p[i] % mod);
  return stored_pow[i][e];
}
int init(int a, int b) {
  if (a == b) return val[a];
  int k = (a + b) / 2;
  f[k].first = 1;
  f[k].second.resize(p.size());
  sum[k] = init(a, k) + init(k + 1, b);
  if (sum[k] >= mod) sum[k] -= mod;
  return sum[k];
}
void push_down(int a, int b) {
  int k = (a + b) / 2;
  if (!lazy[k]) return;
  long long mult = f[k].first;
  for (int i = 0; i < p.size(); i++) {
    mult *= prime_pow(i, f[k].second[i]);
    mult %= mod;
  }
  vector<int> mid, leaf;
  if (a < k)
    mid.push_back((a + k) / 2);
  else
    leaf.push_back(a);
  if (k + 1 < b)
    mid.push_back((k + 1 + b) / 2);
  else
    leaf.push_back(b);
  for (int m : mid) {
    lazy[m] = true;
    sum[m] = sum[m] * mult % mod;
    f[m].first = f[m].first * f[k].first % mod;
    for (int i = 0; i < p.size(); i++) f[m].second[i] += f[k].second[i];
  }
  for (int l : leaf) {
    val[l] = val[l] * mult % mod;
    g[l].first = g[l].first * f[k].first % mod;
    for (int i = 0; i < p.size(); i++) g[l].second[i] += f[k].second[i];
  }
  lazy[k] = false;
  f[k].first = 1;
  fill(f[k].second.begin(), f[k].second.end(), 0);
}
void query1(int a, int b, int l, int r, long long& x,
            pair<long long, vector<int>>& fac) {
  if (a == b) {
    val[a] = val[a] * x % mod;
    g[a].first = g[a].first * fac.first % mod;
    for (int i = 0; i < p.size(); i++) g[a].second[i] += fac.second[i];
    return;
  }
  int k = (a + b) / 2;
  if (a == l && b == r) {
    sum[k] = sum[k] * x % mod;
    lazy[k] = true;
    f[k].first = f[k].first * fac.first % mod;
    for (int i = 0; i < p.size(); i++) f[k].second[i] += fac.second[i];
    return;
  }
  push_down(a, b);
  if (r <= k)
    query1(a, k, l, r, x, fac);
  else if (k + 1 <= l)
    query1(k + 1, b, l, r, x, fac);
  else {
    query1(a, k, l, k, x, fac);
    query1(k + 1, b, k + 1, r, x, fac);
  }
  sum[k] = (a == k ? val[k] : sum[(a + k) / 2]) +
           (k + 1 == b ? val[k + 1] : sum[(k + 1 + b) / 2]);
  if (sum[k] >= mod) sum[k] -= mod;
}
void query2(int a, int b, int i, pair<long long, vector<int>>& fac) {
  if (a == b) {
    g[a].first = g[a].first * fac.first % mod;
    val[a] = g[a].first;
    for (int j = 0; j < p.size(); j++) {
      g[a].second[j] -= fac.second[j];
      val[a] = val[a] * prime_pow(j, g[a].second[j]) % mod;
    }
    return;
  }
  push_down(a, b);
  int k = (a + b) / 2;
  if (i <= k)
    query2(a, k, i, fac);
  else
    query2(k + 1, b, i, fac);
  sum[k] = (a == k ? val[k] : sum[(a + k) / 2]) +
           (k + 1 == b ? val[k + 1] : sum[(k + 1 + b) / 2]);
  if (sum[k] >= mod) sum[k] -= mod;
}
long long query3(int a, int b, int l, int r) {
  if (a == b) return val[a];
  int k = (a + b) / 2;
  if (a == l && b == r) return sum[k];
  push_down(a, b);
  if (r <= k) return query3(a, k, l, r);
  if (k + 1 <= l) return query3(k + 1, b, l, r);
  long long s = query3(a, k, l, k) + query3(k + 1, b, k + 1, r);
  return (s >= mod ? s - mod : s);
}
void print(int a, int b) {
  int k = (a + b) / 2;
  if (a == b) {
    cout << k << ": " << val[k] << " = " << g[k].first << " ";
    for (int i = 0; i < p.size(); i++) {
      if (g[k].second[i] == 0) continue;
      cout << " * " << p[i] << "^" << g[k].second[i] << " ";
    }
    cout << endl;
    return;
  }
  cout << "[" << a << "," << b << "]: ";
  cout << sum[k] << ", mult: " << f[k].first << " ";
  for (int i = 0; i < p.size(); i++) {
    if (f[k].second[i] == 0) continue;
    cout << " * " << p[i] << "^" << f[k].second[i] << " ";
  }
  cout << endl;
  print(a, k);
  print(k + 1, b);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> mod;
  factor_mod();
  for (int i = 0; i < n; i++) {
    cin >> val[i];
    factor(val[i], g[i]);
    val[i] %= mod;
  }
  init(0, n - 1);
  cin >> q;
  while (q--) {
    int t;
    cin >> t;
    if (t == 1) {
      int l, r;
      long long x;
      cin >> l >> r >> x;
      l--;
      r--;
      pair<long long, vector<int>> fac;
      factor(x, fac);
      x %= mod;
      query1(0, n - 1, l, r, x, fac);
    } else if (t == 2) {
      int i;
      long long x;
      cin >> i >> x;
      i--;
      pair<long long, vector<int>> fac;
      factor(x, fac);
      fac.first = quick_exp(fac.first, phi - 1);
      query2(0, n - 1, i, fac);
    } else {
      int l, r;
      cin >> l >> r;
      l--;
      r--;
      cout << query3(0, n - 1, l, r) << "\n";
    }
  }
  return 0;
}
