#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace fast_IO {
#define IOSIZE 100000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
const int N=5e6+10;
const int M=3e7+10;
struct Tree_Array
{
	int n,t[N];
	inline int lowbit(int x){return x&(-x);}
	inline void update(int x,int k){for (;x<=n;x+=lowbit(x))t[x]+=k;return ;}
	inline int query(int x){int tot=0;for (;x;x-=lowbit(x))tot+=t[x];return tot;}
}tr;
int n,m,e[N],phi[M],mod[N],tag,prime[M],cnt;
static bitset<M> vis;
inline void Get_phi()
{
	phi[1]=1;int len=2e7;
	for (int i=2;i<=len;i++)
	{
		if (!vis[i]) prime[++cnt]=i,phi[i]=i-1;
		for (int j=1;j<=cnt and prime[j]<=len/i;j++)
		{
			vis[i*prime[j]]=1;
			if (i%prime[j]) phi[i*prime[j]]=phi[i]*(prime[j]-1);
			else phi[i*prime[j]]=phi[i]*prime[j];
		}
	}
	return ;
}
inline int qpow(int x,int y,int p)
{
	int ans=1;tag=false;
	if (x>=p) x%=p,tag=true;
	while (y)
	{
		if (y&1)
		{
			ans*=x;
			if (ans>=p) tag=true,ans%=p;
		}
		y>>=1;
		x*=x;
		if (x>=p) tag=true,x%=p;
	}
	return ans;
}
signed main()
{
	cin>>n>>m;tr.n=n;
	for (int i=1;i<=n;i++) cin>>e[i];
	for (int i=1;i<=n;i++) tr.update(i,e[i]-e[i-1]);
	Get_phi();
	while (m--)
	{
		int op,l,r,p;
		cin>>op>>l>>r>>p;
		if (op==1) tr.update(l,p),tr.update(r+1,-p);
		if (op==2)
		{
			int it=l;
			mod[it]=p;p=phi[p];
			while (p and it<r) mod[++it]=p,p=phi[p];
			int ans=1;
			for (int i=it;i>=l;i--)
			{
				ans=qpow(tr.query(i),ans,mod[i]);
				if (tag) ans+=mod[i];
			}
			cout<<ans%mod[l]<<endl;
		}
	}
	return (0-0);
}

TLE on #8 and #10 。