#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100000;
const int MAX_K = 10;
int N, Q;
long long MOD, M2 = 1;
int arr[MAX_N + 1];
vector<int> prime;
vector<int> p2;
int gcd(int x, int y) { return (x == 0) ? y : gcd(y % x, x); }
void init() {
  for (int i = 2; i < MAX_N; i++) {
    bool tf = true;
    for (int j : prime) {
      if (i % j == 0) {
        tf = false;
        break;
      }
      if (j * j > i) break;
    }
    if (tf) prime.push_back(i);
  }
  long long T = MOD;
  for (int i : prime) {
    if ((long long)i * (long long)i > T) break;
    if (T % (long long)i == 0) {
      p2.push_back(i);
      T /= i;
      M2 *= (long long)(i - 1);
      while (T % (long long)i == 0) {
        T /= (long long)i;
        M2 *= (long long)i;
      }
    }
  }
  if (T != 1) {
    M2 *= (long long)(T - 1);
    p2.push_back((int)T);
  }
  while (!prime.empty()) prime.pop_back();
  while (!p2.empty()) {
    prime.push_back(p2.back());
    p2.pop_back();
  }
}
long long multi(long long x, long long y) {
  if (y == 0) return 1;
  if (y == 1) return x % MOD;
  long long m = multi(x, y / 2);
  if (y % 2) {
    return (m * m % MOD) * x % MOD;
  }
  return (m * m) % MOD;
}
long long inv(long long x) { return multi(x, M2 - 1); }
int tree[MAX_K + 1][MAX_N + 1];
void add(int x, int y, int z) {
  while (y <= N) {
    tree[x][y] += z;
    y += (y & -y);
  }
}
int sum2(int x, int y) {
  int ret = 0;
  while (y > 0) {
    ret += tree[x][y];
    y -= (y & -y);
  }
  return ret;
}
int sum(int x, int y, int z) { return sum2(x, z) - sum2(x, y - 1); }
struct SEG {
  struct NODE {
    int l, r;
    long long sum, lazy;
  };
  int SZ;
  vector<NODE> seg;
  void add() { seg.push_back({-1, -1, 0, 1LL}); }
  void Init(int x) {
    SZ = x;
    add();
    init(0, 1, SZ);
  }
  void init(int idx, int s, int e) {
    if (s == e) return;
    seg[idx].l = seg.size();
    add();
    seg[idx].r = seg.size();
    add();
    init(seg[idx].l, s, (s + e) / 2);
    init(seg[idx].r, (s + e) / 2 + 1, e);
  }
  void Update(int x, long long y) { update(0, 1, SZ, x, y); }
  void update(int idx, int s, int e, int x, long long y) {
    if (s == e) {
      seg[idx].sum = y % MOD;
      return;
    }
    if (seg[idx].lazy != 1LL) {
      seg[seg[idx].l].sum = (seg[seg[idx].l].sum * seg[idx].lazy) % MOD;
      seg[seg[idx].r].sum = (seg[seg[idx].r].sum * seg[idx].lazy) % MOD;
      seg[seg[idx].l].lazy = (seg[seg[idx].l].lazy * seg[idx].lazy) % MOD;
      seg[seg[idx].r].lazy = (seg[seg[idx].r].lazy * seg[idx].lazy) % MOD;
      seg[idx].lazy = 1LL;
    }
    if (x <= (s + e) / 2) {
      update(seg[idx].l, s, (s + e) / 2, x, y);
    } else {
      update(seg[idx].r, (s + e) / 2 + 1, e, x, y);
    }
    seg[idx].sum = (seg[seg[idx].l].sum + seg[seg[idx].r].sum) % MOD;
  }
  void Multi(int x, int y, long long z) { multi(0, 1, SZ, x, y, z); }
  void multi(int idx, int s, int e, int x, int y, long long z) {
    if (x <= s && e <= y) {
      seg[idx].sum = (seg[idx].sum * z) % MOD;
      seg[idx].lazy = (seg[idx].lazy * z) % MOD;
      return;
    }
    if (x > e || y < s) return;
    if (seg[idx].lazy != 1LL) {
      seg[seg[idx].l].sum = (seg[seg[idx].l].sum * seg[idx].lazy) % MOD;
      seg[seg[idx].r].sum = (seg[seg[idx].r].sum * seg[idx].lazy) % MOD;
      seg[seg[idx].l].lazy = (seg[seg[idx].l].lazy * seg[idx].lazy) % MOD;
      seg[seg[idx].r].lazy = (seg[seg[idx].r].lazy * seg[idx].lazy) % MOD;
      seg[idx].lazy = 1LL;
    }
    multi(seg[idx].l, s, (s + e) / 2, x, y, z);
    multi(seg[idx].r, (s + e) / 2 + 1, e, x, y, z);
    seg[idx].sum = (seg[seg[idx].l].sum + seg[seg[idx].r].sum) % MOD;
  }
  long long Sum(int x, int y) { return sum(0, 1, SZ, x, y); }
  long long sum(int idx, int s, int e, int x, int y) {
    if (x <= s && e <= y) return seg[idx].sum;
    if (x > e || y < s) return 0;
    if (seg[idx].lazy != 1LL) {
      seg[seg[idx].l].sum = (seg[seg[idx].l].sum * seg[idx].lazy) % MOD;
      seg[seg[idx].r].sum = (seg[seg[idx].r].sum * seg[idx].lazy) % MOD;
      seg[seg[idx].l].lazy = (seg[seg[idx].l].lazy * seg[idx].lazy) % MOD;
      seg[seg[idx].r].lazy = (seg[seg[idx].r].lazy * seg[idx].lazy) % MOD;
      seg[idx].lazy = 1LL;
    }
    return (sum(seg[idx].l, s, (s + e) / 2, x, y) +
            sum(seg[idx].r, (s + e) / 2 + 1, e, x, y)) %
           MOD;
  }
} Seg, Seg2;
int main() {
  scanf("%d%lld", &N, &MOD);
  init();
  Seg.Init(N);
  Seg2.Init(N);
  for (int i = 1; i <= N; i++) {
    scanf("%d", &arr[i]);
    Seg2.Update(i, arr[i]);
    for (int j = 0; j < prime.size(); j++) {
      int n = prime[j], cnt = 0;
      if (arr[i] % n == 0) {
        while (arr[i] % n == 0) {
          arr[i] /= n;
          cnt++;
        }
        add(j, i, cnt);
        if (i != N) add(j, i + 1, -cnt);
      }
    }
    Seg.Update(i, arr[i]);
  }
  scanf("%d", &Q);
  while (Q--) {
    int t;
    int l, r, x, p;
    scanf("%d", &t);
    if (t == 1) {
      scanf("%d%d%d", &l, &r, &x);
      Seg2.Multi(l, r, (long long)x);
      for (int i = 0; i < prime.size(); i++) {
        int n = prime[i], cnt = 0;
        if (x % n == 0) {
          while (x % n == 0) {
            x /= n;
            cnt++;
          }
          add(i, l, cnt);
          if (r != N) {
            add(i, r + 1, -cnt);
          }
        }
      }
      if (x != 1) {
        Seg.Multi(l, r, (long long)x);
      }
    } else if (t == 2) {
      scanf("%d%d", &p, &x);
      long long num = 1;
      for (int i = 0; i < prime.size(); i++) {
        int n = prime[i], cnt = 0;
        if (x % n == 0) {
          while (x % n == 0) {
            x /= n;
            cnt++;
          }
          add(i, p, -cnt);
          if (p != N) add(i, p + 1, cnt);
        }
        int c = sum2(i, p);
        num = (num * multi((long long)n, (long long)c)) % MOD;
      }
      long long n = Seg.Sum(p, p);
      n = (n * inv((long long)x)) % MOD;
      num = (num * n) % MOD;
      Seg.Update(p, n);
      Seg2.Update(p, num);
    } else {
      scanf("%d%d", &l, &r);
      printf("%lld\n", Seg2.Sum(l, r));
    }
  }
  return 0;
}
