#include <bits/stdc++.h>
using namespace std;
using li = long long;
using ld = long double;
void solve(bool);
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << fixed << setprecision(20);
  solve(true);
  return 0;
}
const li maxn = (li)1e5 + 5;
li n, q, mod;
vector<li> p_divs;
vector<vector<li> > pw_p_divs;
vector<li> tcnt[4 * maxn];
li t[4 * maxn], tx[4 * maxn], a[maxn];
void mult(li& x, li y) { x = (li)x * y % mod; }
li pw(li x, li y) {
  if (y == 0) return 1;
  if (y & 1) return x * pw(x, y - 1) % mod;
  return pw(x * x % mod, y / 2);
}
void init(li v, li l, li r) {
  if (l > r) return;
  tx[v] = 1;
  tcnt[v].assign(p_divs.size(), 0);
  if (l == r) {
    t[v] = a[l];
    for (li i = 0; i < (li)tcnt[v].size(); ++i) {
      while (t[v] % p_divs[i] == 0) {
        t[v] /= p_divs[i];
        tcnt[v][i]++;
      }
    }
    t[v] %= mod;
    return;
  }
  li m = (l + r) / 2;
  init(2 * v, l, m);
  init(2 * v + 1, m + 1, r);
  li multl = 1, multr = 1;
  for (li i = 0; i < (li)tcnt[v].size(); ++i) {
    mult(multl, pw_p_divs[i][tcnt[2 * v][i]]);
    mult(multr, pw_p_divs[i][tcnt[2 * v + 1][i]]);
  }
  t[v] = ((li)t[2 * v] * multl + (li)t[2 * v + 1] * multr) % mod;
}
void push(li v) {
  mult(tx[2 * v], tx[v]);
  mult(tx[2 * v + 1], tx[v]);
  mult(t[2 * v], tx[v]);
  mult(t[2 * v + 1], tx[v]);
  tx[v] = 1;
  for (li i = 0; i < (li)tcnt[v].size(); ++i) {
    tcnt[2 * v][i] += tcnt[v][i];
    tcnt[2 * v + 1][i] += tcnt[v][i];
    mult(t[v], pw_p_divs[i][tcnt[v][i]]);
    tcnt[v][i] = 0;
  }
}
void multiply(li v, li l, li r, li tl, li tr, li x, vector<li>& vc) {
  if (l > r || tl > tr) return;
  if (l == tl && r == tr) {
    mult(t[v], x);
    mult(tx[v], x);
    for (li i = 0; i < (li)tcnt[v].size(); ++i) {
      tcnt[v][i] += vc[i];
    }
    return;
  }
  push(v);
  li m = (l + r) / 2;
  multiply(2 * v, l, m, tl, min(tr, m), x, vc);
  multiply(2 * v + 1, m + 1, r, max(tl, m + 1), tr, x, vc);
  li multl = 1, multr = 1;
  for (li i = 0; i < (li)tcnt[v].size(); ++i) {
    mult(multl, pw_p_divs[i][tcnt[2 * v][i]]);
    mult(multr, pw_p_divs[i][tcnt[2 * v + 1][i]]);
  }
  t[v] = ((li)t[2 * v] * multl + (li)t[2 * v + 1] * multr) % mod;
}
li getsum(li v, li l, li r, li tl, li tr) {
  if (l > r || tl > tr) return 0;
  if (l == tl && r == tr) {
    li ans = t[v];
    for (li i = 0; i < (li)tcnt[v].size(); ++i) {
      mult(ans, pw_p_divs[i][tcnt[v][i]]);
    }
    return ans;
  }
  push(v);
  li m = (l + r) / 2;
  return (getsum(2 * v, l, m, tl, min(tr, m)) +
          getsum(2 * v + 1, m + 1, r, max(tl, m + 1), tr)) %
         mod;
}
void solve(bool __attribute__((unused)) read) {
  cin >> n >> mod;
  for (li i = 0; i < n; ++i) {
    cin >> a[i];
  }
  li euler = mod;
  li x = mod;
  for (li i = 2; (li)i * i <= mod; ++i) {
    if (x % i == 0) {
      while (x % i == 0) {
        x /= i;
      }
      p_divs.push_back(i);
      pw_p_divs.push_back(vector<li>(1, 1));
      euler = euler * (i - 1) / i;
    }
  }
  if (x != 1) {
    p_divs.push_back(x);
    pw_p_divs.push_back(vector<li>(1, 1));
    euler = euler * (x - 1) / x;
  }
  for (li i = 0; i < (li)p_divs.size(); ++i) {
    for (li j = 1; j < 64; ++j) {
      pw_p_divs[i].push_back((li)pw_p_divs[i].back() * p_divs[i] % mod);
    }
  }
  init(1, 0, n - 1);
  cin >> q;
  for (li i = 0; i < q; ++i) {
    li type;
    cin >> type;
    if (type == 1) {
      li l, r, x;
      vector<li> vc(p_divs.size(), 0);
      cin >> l >> r >> x;
      --l;
      --r;
      for (li j = 0; j < (li)p_divs.size(); ++j) {
        while (x % p_divs[j] == 0) {
          x /= p_divs[j];
          vc[j]++;
          pw_p_divs[j].push_back((li)pw_p_divs[j].back() * p_divs[j] % mod);
        }
      }
      multiply(1, 0, n - 1, l, r, x % mod, vc);
    } else if (type == 2) {
      li p, x;
      vector<li> vc(p_divs.size(), 0);
      cin >> p >> x;
      --p;
      for (li j = 0; j < (li)p_divs.size(); ++j) {
        while (x % p_divs[j] == 0) {
          x /= p_divs[j];
          vc[j]--;
        }
      }
      multiply(1, 0, n - 1, p, p, pw(x, euler - 1), vc);
    } else {
      li l, r;
      cin >> l >> r;
      --l;
      --r;
      cout << getsum(1, 0, n - 1, l, r) << "\n";
    }
  }
}
