#include <bits/stdc++.h>
using namespace std;
void extgcd(long long a, long long b, long long& x, long long& y) {
  if (b == 0) {
    assert(a == 1);
    x = 1, y = 0;
    return;
  }
  extgcd(b, a % b, y, x);
  y -= a / b * x;
}
int inv(int a, int c) {
  long long x, y;
  extgcd(a, c, x, y);
  return (x % c + c) % c;
}
long long modpow(long long a, int b, int c) {
  long long res = 1;
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % c;
    a = a * a % c;
  }
  return res;
}
const int MAXN = 100005, MAXT = 262150;
int num[10], tot, n, m, Q, tn;
struct Value {
  int cnt[10];
  long long rest;
  void clear() {
    memset(cnt, 0, sizeof(cnt));
    rest = 1;
  }
  Value() { clear(); }
  Value& operator*=(int x) {
    for (int i = 0; i < tot; i++)
      while (x % num[i] == 0) x /= num[i], ++cnt[i];
    rest = rest * x % m;
    return *this;
  }
  Value& operator/=(int x) {
    for (int i = 0; i < tot; i++)
      while (x % num[i] == 0) x /= num[i], --cnt[i];
    rest = rest * inv(x, m) % m;
    return *this;
  }
  Value& operator*=(const Value& v) {
    for (int i = 0; i < tot; i++) cnt[i] += v.cnt[i];
    rest = rest * v.rest % m;
    return *this;
  }
  long long get_val() {
    long long res = rest;
    for (int i = 0; i < tot; i++) res = res * modpow(num[i], cnt[i], m) % m;
    return res;
  }
} tag[MAXT];
long long sum[MAXT];
void build(int l = 1, int r = tn, int k = 1) {
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(l, mid, k << 1);
  build(mid + 1, r, k << 1 | 1);
  sum[k] = (sum[k << 1] + sum[k << 1 | 1]) % m;
}
void pushdown(int k) {
  int flag = 1;
  for (int i = 0; i < tot; i++)
    if (tag[k].cnt[i]) {
      flag = 0;
      break;
    }
  if (flag && tag[k].rest == 1) return;
  int ls = k << 1, rs = k << 1 | 1;
  tag[ls] *= tag[k], tag[rs] *= tag[k];
  long long v = tag[k].get_val();
  (sum[ls] *= v) %= m, (sum[rs] *= v) %= m;
  tag[k].clear();
}
void mul(int a, int b, int x, int l = 1, int r = tn, int k = 1) {
  if (a > r || b < l) return;
  if (a <= l && b >= r) {
    tag[k] *= x, (sum[k] *= x) %= m;
    return;
  }
  pushdown(k);
  int mid = (l + r) >> 1;
  mul(a, b, x, l, mid, k << 1);
  mul(a, b, x, mid + 1, r, k << 1 | 1);
  sum[k] = (sum[k << 1] + sum[k << 1 | 1]) % m;
}
void divi(int a, int x, int l = 1, int r = tn, int k = 1) {
  if (l == r) {
    tag[k] /= x;
    sum[k] = tag[k].get_val();
    return;
  }
  int mid = (l + r) >> 1;
  pushdown(k);
  if (a <= mid)
    divi(a, x, l, mid, k << 1);
  else
    divi(a, x, mid + 1, r, k << 1 | 1);
  sum[k] = (sum[k << 1] + sum[k << 1 | 1]) % m;
}
int query(int a, int b, int l = 1, int r = tn, int k = 1) {
  if (a > r || b < l) return 0;
  if (a <= l && b >= r) return sum[k];
  pushdown(k);
  int mid = (l + r) >> 1;
  return (query(a, b, l, mid, k << 1) + query(a, b, mid + 1, r, k << 1 | 1)) %
         m;
}
void pre() {
  int kk = m;
  for (int i = 2; i * i <= kk; i++)
    if (kk % i == 0) {
      while (kk % i == 0) kk /= i;
      num[tot++] = i;
    }
  if (kk > 1) num[tot++] = kk;
}
int main() {
  scanf("%d%d", &n, &m);
  pre();
  for (tn = 1; tn < n; tn <<= 1)
    ;
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &sum[i + tn - 1]);
    tag[i + tn - 1] *= sum[i + tn - 1];
    sum[i + tn - 1] %= m;
  }
  build();
  scanf("%d", &Q);
  while (Q--) {
    int a, b, c, d;
    scanf("%d%d%d", &a, &b, &c);
    if (a == 1) {
      scanf("%d", &d);
      mul(b, c, d);
    } else if (a == 2)
      divi(b, c);
    else
      printf("%d\n", query(b, c));
  }
  return 0;
}
