#include <bits/stdc++.h>
#define int long long

using namespace std;

const int maxn = 5e5 + 10;
const int maxp = 2e7 + 10;

int n, m;
int s[maxn];
int op, l, r, p;

struct bit {
    int n, tr[maxn];
    bit() = default;
    bit(int n): n(n) {}
    int lowbit(int x) { return x & -x; }
    void add(int p, int v) { while (p <= n) tr[p] += v, p += lowbit(p); }
    void add(int l, int r, int v) { add(l, v), add(r + 1, -v); }
    int query(int p) { int tot = 0; while (p) tot += tr[p], p -= lowbit(p); return tot; }
    int operator[] (int p) { return query(p); }
} a;

int pr[maxp >> 4], cnt;
bool bk[maxp];
int phi[maxp];

void sieve() {
    bk[0] = bk[1] = phi[1] = 1;
    for (int i = 2; i < maxp; i++) {
        if (!bk[i]) pr[++cnt] = i, phi[i] = i - 1;
        for (int j = 1; j <= cnt && pr[j] * i < maxp; j++) {
            bk[pr[j] * i] = 1;
            if (i % pr[j] == 0) phi[i * pr[j]] = phi[i] * pr[j], j = cnt + 1;
            else phi[i * pr[j]] = phi[i] * (pr[j] - 1);
        }
    }
}

int power(int a, int b, int p) {
    int r = 1, w = a;
    while (b) {
        if (b & 1) r = r * w % p;
        b >>= 1, w = w * w % p;
    }
    return r;
}

int solve(int l, int r, int p) {
    if (p == 1) return 1;
    if (l == r) return a[l] >= p ? a[l] % p + p : a[l];
    if (a[l] % p == 0) return 0;
    int mid = min(l + 5, r);
    for (int i = l + 1; i <= mid; i++) if (a[i] == 1) mid = i;
    int cur = a[mid];
    for (int i = mid - 1; i >= l + 1; i--) {
        int nw = 1;
        for (int j = 1; j <= cur; j++) {
            nw *= a[i];
            if (nw >= phi[p]) return power(a[l], solve(l + 1, r, phi[p]) % phi[p] + phi[p], p);
        }
        cur = nw;
    }
    return power(a[l], cur, p);
}

signed main() {
    sieve();
    cin >> n >> m, a.n = n;
    for (int i = 1; i <= n; i++) cin >> s[i], a.add(i, i, s[i]);
    while (m--) {
        cin >> op >> l >> r >> p;
        if (op == 1) a.add(l, r, p);
        else cout << solve(l, r, p) % p << endl;
    }
    return 0;
}