#include<bits/stdc++.h>
#define pb push_back
#define ull unsigned long long
#define bi bitset<80001>
using namespace std;
const int B=300,N=80000;
int n,q,z[N+1],opt[N+5],ql[N+5],qr[N+5],qu[N+5],up[N+5][19];
bi f[N+1],g[N+1],Now,I;
int tl[300],tr[300],tt,dep[80005];
int bl(int x){return ((x-1)/B+1);}
vector<int>road[N+5],Ql[N+5],Qr[N+5],vec[N+5];
int st[19][N+5],lg[N+5];
int lca(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	for(int i=18;i>=0;--i)if(up[u][i]&&dep[up[u][i]]>=dep[v])u=up[u][i];
	if(u==v)return u;
	for(int i=18;i>=0;--i)if(up[u][i]!=up[v][i])u=up[u][i],v=up[v][i];
	return up[u][0];
}
int qry(int l,int r){
	int len=lg[r-l+1];
	return lca(st[len][l],st[len][r-(1<<len)+1]);
}
void dfs(int u,int fa){
	f[u][u]=1;
	for(int i=1;(1<<i)<=dep[u];++i)up[u][i]=up[up[u][i-1]][i-1];
	for(int v:road[u]){
		if(v==fa)continue;
		dep[v]=dep[u]+1,f[v]=f[u],up[v][0]=u;
		dfs(v,u);
	}
}
const int mod=20242024,sd=19901991;
int gd[N+5],Ans[N+5],prime[N+5],tot,ip[N+5];
void init(){
	for(int i=2;i<=N;++i){
		if(!ip[i])prime[++tot]=i;
		for(int j=1;j<=tot&&prime[j]*i<=N;++j){
			ip[prime[j]*i]=1;
			if(i%prime[j]==0)break;
		}
	}
}
map<int,int>vis;
void solve(int X,int p,int lst){
	for(auto v:vec[X]){
	    g[v]&=Now,g[v]>>=(ql[v]-1),g[v][0]=0;
	    int ct=(g[v]&(I>>(n-qr[v]+ql[v]-1))).count();
	    Ans[v]=(1ll*ct*sd+qr[v]-ql[v]+1-ct)%mod;
	}
	for(int i=p;i<=tot&&1ll*X*prime[i]<=N;++i){
		int np=prime[i];if(i==p)np*=lst;
		for(int j=np;j<=n;j+=np)gd[j]*=prime[i],Now[j]=z[gd[j]];
		solve(X*prime[i],i,np);
		for(int j=np;j<=n;j+=np)gd[j]/=prime[i],Now[j]=z[gd[j]];
	}
}
int main(){
	init(),cin>>n>>q;
	for(int i=1;i<=n;++i)scanf("%d",&z[i]),st[0][i]=i,z[i]&=1,I[i]=1,gd[i]=1;
	for(int i=2;i<=n;++i)lg[i]=lg[i>>1]+1;
	for(int i=1;i<n;++i){
		int u,v;scanf("%d%d",&u,&v);
		road[u].pb(v),road[v].pb(u);
	}dfs(1,-1);
	for(int j=1;(1<<j)<=n;++j)
	 for(int i=1;i+(1<<j)-1<=n;++i)st[j][i]=lca(st[j-1][i],st[j-1][i+(1<<j-1)]);
	for(int l=1;l<=n;l+=B)++tt,tl[tt]=l,tr[tt]=min(l+B-1,n);
	for(int i=1;i<=q;++i){
		scanf("%d",&opt[i]);
		if(opt[i]&1){
			scanf("%d%d",&ql[i],&qr[i]);
			if(bl(ql[i])==bl(qr[i]))for(int j=ql[i];j<=qr[i];++j)g[i]|=f[j];
			else{
				int x=bl(ql[i]),y=bl(qr[i]);
				Ql[ql[i]].pb(i),Qr[qr[i]].pb(i);
				if(y-x>1)Ql[tl[x+1]].pb(i),Qr[tr[y-1]].pb(i);
			}
		}else scanf("%d%d%d",&ql[i],&qr[i],&qu[i]);
	}
	for(int i=1;i<=tt;++i){
		Now.reset();
		for(int j=tl[i];j<=n;++j){
			int p=j;
			while(p&&!Now[p])Now[p]=1,p=up[p][0];
			for(auto v:Qr[j]){
				if(qr[v]==j&&i==bl(j))g[v]|=Now;
				if(qr[v]>j&&i==bl(ql[v])+1)g[v]|=Now;
			}
		}
		Now.reset();
		for(int j=tr[i];j>=1;--j){
			int p=j;
			while(p&&!Now[p])Now[p]=1,p=up[p][0];
			for(auto v:Ql[j]){
				if(ql[v]==j&&i==bl(j))g[v]|=Now;
				if(ql[v]<j&&i==bl(qr[v])-1)g[v]|=Now;
			}
		}
	}
	Now.reset();
	for(int i=1;i<=q;++i)
	    if(opt[i]&1){
	    	int t=qry(ql[i],qr[i]);
			if(t>1)g[i]^=f[up[t][0]];
			Now^=g[i];
		}else g[i]=Now,vec[qu[i]].pb(i);
	Now.reset();
	for(int i=1;i<=n;++i)Now[i]=z[gd[i]];
	solve(1,1,1);
	for(int i=1;i<=q;++i)if(opt[i]==2)printf("%d\n",Ans[i]);
	return 0;
}