#include <bits/stdc++.h>
using namespace std;
long long expo(long long base, long long exponent, long long mod) {
  long long ans = 1;
  while (exponent != 0) {
    if (exponent & 1) ans = (1LL * ans * base) % mod;
    base = (1LL * base * base) % mod;
    exponent >>= 1;
  }
  return ans % mod;
}
const long long N = 100005;
long long n, mod, q;
vector<long long> primes;
long long a[N];
long long seg1[4 * N], lazy1[4 * N];
long long seg2[4 * N][10], lazy2[4 * N][10];
long long seg3[4 * N], lazy3[4 * N];
void build(long long node, long long start, long long end) {
  lazy1[node] = lazy3[node] = 1;
  if (start == end) {
    seg1[node] = a[start] % mod;
    for (long long i = 0; i < (long long)primes.size(); i++) {
      while (a[start] % primes[i] == 0) a[start] /= primes[i], seg2[node][i]++;
    }
    seg3[node] = a[start] % mod;
    return;
  }
  long long mid = (start + end) >> 1;
  build(node << 1, start, mid);
  build(node << 1 | 1, mid + 1, end);
  seg1[node] = (seg1[node << 1] + seg1[node << 1 | 1]) % mod;
  for (long long i = 0; i < (long long)primes.size(); i++)
    seg2[node][i] = seg2[node << 1][i] + seg2[node << 1 | 1][i];
  seg3[node] = (seg3[node << 1] + seg3[node << 1 | 1]) % mod;
}
void update11(long long node, long long start, long long end, long long l,
              long long r, long long val) {
  if (lazy1[node] != 1) {
    seg1[node] = seg1[node] * lazy1[node] % mod;
    if (start != end) {
      lazy1[node << 1] = lazy1[node << 1] * lazy1[node] % mod;
      lazy1[node << 1 | 1] = lazy1[node << 1 | 1] * lazy1[node] % mod;
    }
    lazy1[node] = 1;
  }
  if (start > end || start > r || end < l) return;
  if (l <= start && end <= r) {
    seg1[node] = seg1[node] * val % mod;
    if (start != end) {
      lazy1[node << 1] = lazy1[node << 1] * val % mod;
      lazy1[node << 1 | 1] = lazy1[node << 1 | 1] * val % mod;
    }
    return;
  }
  long long mid = (start + end) >> 1;
  update11(node << 1, start, mid, l, r, val);
  update11(node << 1 | 1, mid + 1, end, l, r, val);
  seg1[node] = (seg1[node << 1] + seg1[node << 1 | 1]) % mod;
}
void update12(long long node, long long start, long long end, long long p,
              long long val) {
  if (start == end) {
    seg1[node] = val % mod;
    lazy1[node] = 1;
    return;
  }
  if (lazy1[node] != 1) {
    seg1[node] = seg1[node] * lazy1[node] % mod;
    if (start != end) {
      lazy1[node << 1] = lazy1[node << 1] * lazy1[node] % mod;
      lazy1[node << 1 | 1] = lazy1[node << 1 | 1] * lazy1[node] % mod;
    }
    lazy1[node] = 1;
  }
  long long mid = (start + end) >> 1;
  if (p <= mid) {
    update12(node << 1, start, mid, p, val);
    seg1[node] =
        (seg1[node << 1] + lazy1[node << 1 | 1] * seg1[node << 1 | 1]) % mod;
  } else {
    update12(node << 1 | 1, mid + 1, end, p, val);
    seg1[node] =
        (lazy1[node << 1] * seg1[node << 1] + seg1[node << 1 | 1]) % mod;
  }
}
long long query1(long long node, long long start, long long end, long long l,
                 long long r) {
  if (start > end || start > r || end < l) return 0;
  if (lazy1[node] != 1) {
    seg1[node] = seg1[node] * lazy1[node] % mod;
    if (start != end) {
      lazy1[node << 1] = lazy1[node << 1] * lazy1[node] % mod;
      lazy1[node << 1 | 1] = lazy1[node << 1 | 1] * lazy1[node] % mod;
    }
    lazy1[node] = 1;
  }
  if (start >= l && end <= r) return seg1[node] % mod;
  long long mid = (start + end) >> 1;
  long long q1 = query1(node << 1, start, mid, l, r);
  long long q2 = query1(node << 1 | 1, mid + 1, end, l, r);
  return (q1 + q2) % mod;
}
void update2(long long node, long long start, long long end, long long l,
             long long r, long long val, long long f) {
  if (lazy2[node][f] != 0) {
    seg2[node][f] += (end - start + 1) * lazy2[node][f];
    if (start != end) {
      lazy2[node << 1][f] += lazy2[node][f];
      lazy2[node << 1 | 1][f] += lazy2[node][f];
    }
    lazy2[node][f] = 0;
  }
  if (start > end || start > r || end < l) return;
  if (l <= start && end <= r) {
    seg2[node][f] += (end - start + 1) * val;
    if (start != end) {
      lazy2[node << 1][f] += val;
      lazy2[node << 1 | 1][f] += val;
    }
    return;
  }
  long long mid = (start + end) >> 1;
  update2(node << 1, start, mid, l, r, val, f);
  update2(node << 1 | 1, mid + 1, end, l, r, val, f);
  seg2[node][f] = seg2[node << 1][f] + seg2[node << 1 | 1][f];
}
long long query2(long long node, long long start, long long end, long long l,
                 long long r, long long f) {
  if (start > end || start > r || end < l) return 0;
  if (lazy2[node][f] != 0) {
    seg2[node][f] += (end - start + 1) * lazy2[node][f];
    if (start != end) {
      lazy2[node << 1][f] += lazy2[node][f];
      lazy2[node << 1 | 1][f] += lazy2[node][f];
    }
    lazy2[node][f] = 0;
  }
  if (start >= l && end <= r) return seg2[node][f];
  long long mid = (start + end) >> 1;
  long long q1 = query2(node << 1, start, mid, l, r, f);
  long long q2 = query2(node << 1 | 1, mid + 1, end, l, r, f);
  return q1 + q2;
}
void update3(long long node, long long start, long long end, long long l,
             long long r, long long val) {
  if (lazy3[node] != 1) {
    seg3[node] = seg3[node] * lazy3[node] % mod;
    if (start != end) {
      lazy3[node << 1] = lazy3[node << 1] * lazy3[node] % mod;
      lazy3[node << 1 | 1] = lazy3[node << 1 | 1] * lazy3[node] % mod;
    }
    lazy3[node] = 1;
  }
  if (start > end || start > r || end < l) return;
  if (l <= start && end <= r) {
    seg3[node] = seg3[node] * val % mod;
    if (start != end) {
      lazy3[node << 1] = lazy3[node << 1] * val % mod;
      lazy3[node << 1 | 1] = lazy3[node << 1 | 1] * val % mod;
    }
    return;
  }
  long long mid = (start + end) >> 1;
  update3(node << 1, start, mid, l, r, val);
  update3(node << 1 | 1, mid + 1, end, l, r, val);
  seg3[node] = (seg3[node << 1] + seg3[node << 1 | 1]) % mod;
}
long long query3(long long node, long long start, long long end, long long l,
                 long long r) {
  if (start > end || start > r || end < l) return 0;
  if (lazy3[node] != 1) {
    seg3[node] = seg3[node] * lazy3[node] % mod;
    if (start != end) {
      lazy3[node << 1] = lazy3[node << 1] * lazy3[node] % mod;
      lazy3[node << 1 | 1] = lazy3[node << 1 | 1] * lazy3[node] % mod;
    }
    lazy3[node] = 1;
  }
  if (start >= l && end <= r) return seg3[node] % mod;
  long long mid = (start + end) >> 1;
  long long q1 = query3(node << 1, start, mid, l, r);
  long long q2 = query3(node << 1 | 1, mid + 1, end, l, r);
  return (q1 + q2) % mod;
}
void solve() {
  cin >> n >> mod;
  long long cur = mod, phi = mod;
  for (long long i = 2; i * i <= cur; ++i) {
    if (cur % i == 0) {
      primes.push_back(i);
      while (cur % i == 0) cur /= i;
      phi = phi / i * (i - 1);
    }
  }
  if (cur > 1) primes.push_back(cur), phi = phi / cur * (cur - 1);
  for (long long i = 1; i < n + 1; i++) cin >> a[i];
  build(1, 1, n);
  cin >> q;
  while (q--) {
    long long type;
    cin >> type;
    if (type == 1) {
      long long l, r, first;
      cin >> l >> r >> first;
      update11(1, 1, n, l, r, first);
      for (long long i = 0; i < (long long)primes.size(); i++) {
        long long cnt = 0;
        while (first % primes[i] == 0) cnt++, first /= primes[i];
        if (cnt) update2(1, 1, n, l, r, cnt, i);
      }
      update3(1, 1, n, l, r, first);
    } else if (type == 2) {
      long long p, first, val = 1;
      cin >> p >> first;
      for (long long i = 0; i < (long long)primes.size(); i++) {
        long long cnt = 0;
        while (first % primes[i] == 0) cnt++, first /= primes[i];
        if (cnt) update2(1, 1, n, p, p, -cnt, i);
        val = val * expo(primes[i], query2(1, 1, n, p, p, i), mod) % mod;
      }
      first = expo(first, phi - 1, mod);
      update3(1, 1, n, p, p, first);
      update12(1, 1, n, p, query3(1, 1, n, p, p) * val % mod);
    } else {
      long long l, r;
      cin >> l >> r;
      cout << query1(1, 1, n, l, r) % mod << '\n';
    }
  }
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long t = 1;
  while (t--) {
    solve();
  }
  return 0;
}
