#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5010;
int n, m, a[N], op, l, r, x;

int ksm(int x, int k, int p) {
    int res = 1;
	while (k != 0) {
        if (k % 2 == 1) res = res * x % p;
        x = x * x % p;
        k /= 2;
    }
    return res % p;
}

signed main() {
	freopen("sjjgt.in", "r", stdin);
	freopen("sjjgt.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= m; i++) {
		cin >> op >> l >> r >> x;
		if (op == 1) for (int j = l; j <= r; j++) a[j] += x;
		else cout << ksm(a[l], a[r], x) << "\n";
	}
	return 0;
}