本地AC，提交RE

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define repp(i,a,b) for(int i=(a);i<(b);++i)
#define perr(i,a,b) for(int i=(a);i>(b);--i)

using namespace std;

typedef long long ll;

const int maxn = 5e5 + 10;
int n;
struct BIT {
    ll c[ maxn ];
    void add( int x, int v ) {
        for( ; x <= n + 1; x += x & ( -x ) ) c[ x ] += v;
        c[ x ] += v;
    }
    ll qry( int x ) {
        ll ret = 0;
        for( ; x; x -= x & ( -x ) ) ret += c[ x ];
        return ret;
    }
} bitre;


const int maxS = 2e7 + 10;
int Prime[ maxS ], vp[ maxS ], phi[ maxS ], low[ maxS ], tot;
void seive( int n ) {
    tot = -1; phi[ 1 ] = vp[ 1 ] = 1; low[ 1 ] = 0;
    rep( i,2,n ) {
        if( !vp[ i ] ) {
            Prime[ ++ tot ] = i;
            phi[ i ] = i - 1;
            low[ i ] = i;
        }
        for( int j = 0; j <= tot && 1ll * i * Prime[ j ] <= n; ++ j ) {
            vp[ i * Prime[ j ] ] = 1;
            if( i % Prime[ j ] == 0 ) {
                low[ i * Prime[ j ] ] = low[ i ] * Prime[ j ];
                if( low[ i ] == i ) phi[ i * Prime[ j ] ] = phi[ i ] * Prime[ j ];
                else phi[ i * Prime[ j ] ] = phi[ i / low[ i ] ] * phi[ low[ i ] * Prime[ j ] ];
                break;
            }
            phi[ i * Prime[ j ] ] = phi[ i ] * ( Prime[ j ] - 1 );
            low[ i * Prime[ j ] ] = Prime[ j ];
        }
    }
}

inline ll md( ll x, ll mod ) {
    return x >= mod ? x % mod + mod : x;
}

ll quickPow( ll x, ll y, ll mod ) {
    ll res = md( 1, mod );
    for( ; y; y >>= 1 ) {
        if( y & 1 ) res = md( res * x, mod );
        x = md( x * x, mod );
    }
    return res;
}

ll work( int l, int r, ll mod ) {
    ll cur = md( bitre.qry( l ), mod );
    if( l == r || mod == 1 ) return md( cur, mod );
    return quickPow( cur, work( l + 1, r, phi[ mod ] ), mod );
}

signed main (  ) {
    if( fopen( "yl.in", "r" ) ) {
        freopen( "yl.in", "r", stdin );
        freopen( "yl.out", "w", stdout );
    }
    ios::sync_with_stdio( false );
    cin.tie( NULL );
    seive( 2e7 );
    ll q, opt, l, r, p, tmp;
    cin >> n >> q;
    rep( i,1,n ) {
        cin >> tmp;
        bitre.add( i, tmp );
        bitre.add( i + 1, -tmp );
    }
    rep( qr,1,q ) {
        cin >> opt >> l >> r >> p;
        if( opt == 1 ) {
            bitre.add( l, p );
            bitre.add( r + 1, -p );
        } else {
            cout << work( l, r, p ) % p << endl;
        }
    }
    return 0;
}