#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
void ckmin(T &a, U b) {
  if (a > b) a = b;
}
template <class T, class U>
void ckmax(T &a, U b) {
  if (a < b) a = b;
}
int N, Q;
long long MOD, PHI = 1;
long long arr[100013];
vector<long long> primes;
pair<vector<long long>, long long> leaf[100013];
pair<vector<long long>, pair<long long, long long> > lazy[3 * 100013];
long long stor[3 * 100013];
long long expo(long long a, long long e) {
  if (e == 0) return 1ll;
  long long res = expo(a * a % MOD, e >> 1);
  if (e & 1) {
    res *= a;
    res %= MOD;
  }
  return res;
}
pair<vector<long long>, pair<long long, long long> > get(long long x) {
  pair<vector<long long>, pair<long long, long long> > res;
  res.first.resize(((int)((primes).size())));
  res.second.second = x;
  for (auto i = (0); i < (((int)((primes).size()))); i++) {
    long long p = primes[i];
    while (x % p == 0) {
      res.first[i]++;
      x /= p;
    }
  }
  res.second.first = x;
  return res;
}
long long get(pair<vector<long long>, long long> x) {
  long long res = x.second;
  for (auto i = (0); i < (((int)((primes).size()))); i++) {
    res *= expo(primes[i], x.first[i]);
    res %= MOD;
  }
  return res;
}
void build(int w, int L, int R) {
  lazy[w].first.resize(((int)((primes).size())));
  lazy[w].second = {1, 1};
  if (L == R) {
    stor[w] = arr[L] % MOD;
    auto a = get(arr[L]);
    leaf[L] = {a.first, a.second.first};
    return;
  }
  int mid = (L + R) >> 1;
  build(w << 1, L, mid);
  build(w << 1 | 1, mid + 1, R);
  stor[w] = stor[w << 1] + stor[w << 1 | 1];
  if (stor[w] >= MOD) stor[w] -= MOD;
}
void push(int w, int L, int R) {
  if (lazy[w].second == make_pair(1ll, 1ll)) {
    return;
  }
  stor[w] *= lazy[w].second.second;
  stor[w] %= MOD;
  if (L != R) {
    for (auto i = (0); i < (((int)((primes).size()))); i++) {
      lazy[w << 1].first[i] += lazy[w].first[i];
      lazy[w << 1 | 1].first[i] += lazy[w].first[i];
    }
    lazy[w << 1].second.first *= lazy[w].second.first;
    lazy[w << 1].second.first %= MOD;
    lazy[w << 1 | 1].second.first *= lazy[w].second.first;
    lazy[w << 1 | 1].second.first %= MOD;
    lazy[w << 1].second.second *= lazy[w].second.second;
    lazy[w << 1].second.second %= MOD;
    lazy[w << 1 | 1].second.second *= lazy[w].second.second;
    lazy[w << 1 | 1].second.second %= MOD;
  } else {
    for (auto i = (0); i < (((int)((primes).size()))); i++) {
      leaf[L].first[i] += lazy[w].first[i];
    }
    leaf[L].second *= lazy[w].second.first;
    leaf[L].second %= MOD;
  }
  for (auto i = (0); i < (((int)((primes).size()))); i++) {
    lazy[w].first[i] = 0;
  }
  lazy[w].second = {1, 1};
  return;
}
void rangeupdate(int w, int L, int R, int a, int b,
                 pair<vector<long long>, pair<long long, long long> > v) {
  push(w, L, R);
  if (b < L || R < a) return;
  if (a <= L && R <= b) {
    for (auto i = (0); i < (((int)((primes).size()))); i++) {
      lazy[w].first[i] += v.first[i];
    }
    lazy[w].second.first *= v.second.first;
    lazy[w].second.first %= MOD;
    lazy[w].second.second *= v.second.second;
    lazy[w].second.second %= MOD;
    push(w, L, R);
    return;
  }
  int mid = (L + R) >> 1;
  rangeupdate(w << 1, L, mid, a, b, v);
  rangeupdate(w << 1 | 1, mid + 1, R, a, b, v);
  stor[w] = stor[w << 1] + stor[w << 1 | 1];
  if (stor[w] >= MOD) stor[w] -= MOD;
}
void update(int w, int L, int R, int a,
            pair<vector<long long>, pair<long long, long long> > v) {
  push(w, L, R);
  if (a < L || R < a) {
    return;
  }
  if (L == R) {
    for (auto i = (0); i < (((int)((primes).size()))); i++) {
      leaf[L].first[i] -= v.first[i];
    }
    long long part = v.second.first;
    part = expo(part, PHI - 1);
    leaf[L].second *= part;
    leaf[L].second %= MOD;
    stor[w] = get(leaf[L]);
    return;
  }
  int mid = (L + R) >> 1;
  update(w << 1, L, mid, a, v);
  update(w << 1 | 1, mid + 1, R, a, v);
  stor[w] = stor[w << 1] + stor[w << 1 | 1];
  if (stor[w] >= MOD) stor[w] -= MOD;
}
long long query(int w, int L, int R, int a, int b) {
  push(w, L, R);
  if (a <= L && R <= b) {
    return stor[w];
  }
  int mid = (L + R) >> 1;
  long long res = 0;
  if (a <= mid) res += query(w << 1, L, mid, a, b);
  if (mid < b) res += query(w << 1 | 1, mid + 1, R, a, b);
  if (res >= MOD) res -= MOD;
  return res;
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(12);
  cerr << fixed << setprecision(4);
  cin >> N >> MOD;
  for (auto i = (0); i < (N); i++) {
    cin >> arr[i];
  }
  long long tmp = MOD;
  for (int i = 2; i * i <= MOD; i++) {
    if (tmp % i) continue;
    primes.push_back(i);
    tmp /= i;
    PHI *= (i - 1);
    while (tmp % i == 0) {
      tmp /= i;
      PHI *= i;
    }
  }
  if (tmp != 1) {
    primes.push_back(tmp);
    PHI *= (tmp - 1);
  }
  build(1, 0, N - 1);
  cin >> Q;
  while (Q--) {
    int qid;
    cin >> qid;
    if (qid == 1) {
      int l, r;
      long long x;
      cin >> l >> r >> x;
      l--;
      r--;
      rangeupdate(1, 0, N - 1, l, r, get(x));
    }
    if (qid == 2) {
      int p;
      long long x;
      cin >> p >> x;
      p--;
      update(1, 0, N - 1, p, get(x));
    }
    if (qid == 3) {
      int l, r;
      cin >> l >> r;
      l--;
      r--;
      long long ans = query(1, 0, N - 1, l, r);
      cout << ans << '\n';
    }
  }
  return 0;
}
