#include<iostream>
using namespace std;

#define int long long
const int MAXN = 2 * 1e7 + 5;
int pri[MAXN], phi[MAXN];
bool vis[MAXN];
int n, m, a[MAXN];
int sum[MAXN], tot = 0;

void init(){
    phi[1] = 1;
    for(int i = 2;i < MAXN;i ++){
        if(!vis[i]){
            pri[++ tot] = i;
            phi[i] = i - 1;
        }
        for(int j = 1;j <= tot && i * pri[j] < MAXN;j ++){
            vis[i * pri[j]] = 1;
            if(i % pri[j] == 0){
                phi[i * pri[j]] = phi[i] * pri[j];
                break;
            }
            else phi[i * pri[j]] = phi[i] * (pri[j] - 1);
        }
    }
//    for(int i = 1;i <= 10;i ++) cout << phi[i] << ' ';
}

int lowbit(int x){
    return x & -x;
}

void add(int x, int k){
    while(x <= n){
        sum[x] += k;
        x += lowbit(x);
    }
}

int ask(int x){
    int res = 0;
    while(x){
        res += sum[x];
        x -= lowbit(x);
    }
    return res;
}

int qpow(int a, int b, int p){
    int res = 1;
    bool flag = 0;
    if(a >= p){
        a %= p;
        flag = 1;
    }
    while(b){
        if(b & 1) res = res * a;
        if(res >= p){
            flag = 1;
            res %= p;
        }
        a = a * a;
        if(a >= p){
            a %= p;
            flag = 1;
        }
        b >>= 1;
    }
    return flag ? res % p + p : res;
}

int solve(int l, int r, int p){
    int val = a[l] + ask(l);
    if(p == 1) return 1;
    if(l == r) return val >= p ? val % p + p : val;
    int cnt = solve(l + 1, r, phi[p]);
    return qpow(val, cnt, p);
}

signed main(){
    freopen("sjjgt.in", "r", stdin);
    freopen("sjjgt.out", "w", stdout);
    init();
    cin >> n >> m;
    
    for(int i = 1;i <= n;i ++){
        cin >> a[i];
    }
    for(int i = 1;i <= m;i ++){
        int op, l, r, x;
        cin >> op >> l >> r >> x;
        if(op == 1) add(l, x), add(r + 1, -x);
        else cout << solve(l, r, x) % x << '\n';
    }
    
    return 0;
}