#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 500005
#define M 20000005
#define int long long
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define rf(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
int n,m,k,a[N],b[N],t[N],ans,op,x,y,z;
int p[M],cnt,phi[M];
bool vis[M],f;
void swap(int &x,int &y){int t=x;x=y;y=t;}
int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
void init()
{
    phi[1]=1;
    fo(i,2,M-1)
    {
        if(!vis[i])p[++cnt]=i,phi[i]=i-1;
        fo(j,1,cnt)
        {
            if(i*p[j]>=M)break;
            vis[i*p[j]]=1;
            if(!(i%p[j]))
            {
                phi[i*p[j]]=phi[i]*p[j];
                break;
            }
            phi[i*p[j]]=phi[i]*(p[j]-1);
        }
    }
}
void bd()
{
    fo(i,1,n)
        if(i+(i&-i)<=n)
            t[i+(i&-i)]+=t[i];
}
void ud(int l,int r,int k)
{
    for(int x=l;x<=n;x+=x&-x)
        t[x]+=k;
    for(int x=r+1;x<=n;x+=x&-x)
        t[x]-=k;
}
int gs(int x)
{
    int sum=0;
    for(;x;x&=x-1)
        sum+=t[x];
    return sum;
}
int fp(int a,int n,int p)
{
    int ans=1;
    while(n)
    {
        if(a>=p)a%=p,f=1;
        if(n&1)
        {
            ans*=a;
            if(ans>=p)ans%=p,f=1;
        }
        a*=a;
        n>>=1;
    }
    return ans;
}
int solve(int l,int r,int p)
{
    if(p==1)return 0;
    if(l==r)return gs(l)%p;
    y=1;//幂次为y
    f=0;//x<phi(p)
    a[l]=gs(l);b[l]=p;
    fo(i,l+1,r)
    {
        a[i]=gs(i);b[i]=phi[b[i-1]];
        if(a[i]==1||b[i]==1)
        {
            r=i-1;
            y=b[i]==1?0:1;
            f=a[i]>=b[i];
            break;
        }
    }
    rf(i,r,l)
    {
        if(f)y+=phi[b[i]];
        y=fp(a[i],y,b[i]);
    }
    return y;
}
int read(){
    int sum=0;bool f=0;char c=getchar();
    for(;c<48||c>57;c=getchar())if(c==45)f=1;
    for(;c>=48&&c<=57;c=getchar())sum=sum*10+(c&15);
    return f?-sum:sum;
}
signed main(){
    freopen("sjjgt.in","r",stdin);freopen("sjjgt.out","w",stdout);
    init();
    n=read();m=read();
    fo(i,1,n)t[i]=read();
    rf(i,n,1)t[i]-=t[i-1];
    bd();
    while(m--)
    {
        op=read();x=read();y=read();z=read();
        if(op==1)ud(x,y,z);
        else printf("%lld\n",solve(x,y,z));
    }
    return 0;
}