#include<bits/stdc++.h>
using namespace std;
const int MAXN=8e4+5,B=282,X=19901991,Y=20242024;
int n,q,z[MAXN],bel[MAXN],lp[MAXN],rp[MAXN];
vector <int> G[MAXN];
int fa[MAXN],dfn[MAXN],dcnt,st[MAXN][18],dl[MAXN][18],dr[MAXN][18];
int bit(int x) { return 1<<x; }
int cmp(int x,int y) { return dfn[x]<dfn[y]?x:y; }
int qdl(int l,int r) {
	int k=__lg(r-l+1);
	return min(dl[l][k],dl[r-bit(k)+1][k]);
}
int qdr(int l,int r) {
	int k=__lg(r-l+1);
	return max(dr[l][k],dr[r-bit(k)+1][k]);
}
int lca(int l,int r) {
	int k=__lg(r-l+1);
	return cmp(st[l][k],st[r-bit(k)+1][k]);
}
void dfs0(int u,int fz) {
	fa[u]=fz,dl[u][0]=dr[u][0]=dfn[u]=++dcnt,st[dcnt][0]=fz;
	for(int v:G[u]) if(v^fz) dfs0(v,u);
}
int op[MAXN],ql[MAXN],qr[MAXN];
bitset <MAXN> F[MAXN],S;
vector <int> wl[MAXN],wr[MAXN],wx[MAXN],LCA[MAXN];
void add(bitset<MAXN>&s,int u) { for(;u&&!s[u];u=fa[u]) s.set(u); }
void dfs1(int u) {
	S.set(u);
	for(int i:LCA[u]) F[i]^=S;
	for(int v:G[u]) if(v^fa[u]) dfs1(v);
	S.reset(u);
}
int pr[MAXN],tot,g[MAXN];
bool isc[MAXN];
void dfs2(int o,int x) {
	if(o>tot) {
		for(int i:wx[x]) F[i]^=S;
		return ;
	}
	int p=pr[o],pw=1;
	dfs2(o+1,x);
	while(x<=n) {
		if(1ll*x*p>n) break;
		x*=p,pw*=p;
		for(int i=pw;i<=n;i+=pw) S[i]=z[g[i]*=p];
		dfs2(o+1,x);
	}
	for(int i=p;i<=n;i+=p) {
		while(g[i]%p==0) g[i]/=p;
		S[i]=z[g[i]];
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin>>n>>q;
	for(int i=1;i<=n;++i) cin>>z[i],z[i]&=1;
	for(int i=1;(i-1)*B+1<=n;++i) {
		lp[i]=(i-1)*B+1,rp[i]=min(i*B,n);
		fill(bel+lp[i],bel+rp[i]+1,i);
	}
	for(int i=1,u,v;i<n;++i) cin>>u>>v,G[u].push_back(v),G[v].push_back(u);
	dfs0(1,0);
	for(int k=1;k<18;++k) for(int i=1;i+bit(k)-1<=n;++i) {
		st[i][k]=cmp(st[i][k-1],st[i+bit(k-1)][k-1]);
		dl[i][k]=min(dl[i][k-1],dl[i+bit(k-1)][k-1]);
		dr[i][k]=max(dr[i][k-1],dr[i+bit(k-1)][k-1]);
	}
	for(int i=1,x;i<=q;++i) {
		cin>>op[i]>>ql[i]>>qr[i];
		if(op[i]==1) {
			LCA[lca(qdl(ql[i],qr[i])+1,qdr(ql[i],qr[i]))].push_back(i);
			if(bel[ql[i]]==bel[qr[i]]) for(int u=ql[i];u<=qr[i];++u) add(F[i],u);
			else wl[bel[ql[i]]].push_back(i),wr[bel[ql[i]]+1].push_back(i);
		} else cin>>x,wx[x].push_back(i);
	}
	for(int o=1;o<=bel[n];++o) {
		sort(wl[o].begin(),wl[o].end(),[&](int x,int y){ return ql[x]>ql[y]; });
		sort(wr[o].begin(),wr[o].end(),[&](int x,int y){ return qr[x]<qr[y]; });
		S.reset();
		for(int i=lp[o],j=0,s=wr[o].size();j<s&&i<=n;++i) {
			add(S,i);
			while(j<s&&qr[wr[o][j]]==i) F[wr[o][j++]]|=S;
		}
		S.reset();
		for(int i=rp[o],j=0,s=wl[o].size();j<s&&i>=lp[o];--i) {
			add(S,i);
			while(j<s&&ql[wl[o][j]]==i) F[wl[o][j++]]|=S;
		}
	}
	S.reset(),dfs1(1);
	for(int i=1;i<=q;++i) F[i]^=F[i-1];
	for(int i=2;i<=n;++i) if(!isc[i]) {
		pr[++tot]=i;
		for(int j=2*i;j<=n;j+=i) isc[j]=true;
	}
	S.reset();
	for(int i=1;i<=n;++i) S[i]=z[g[i]=1];
	dfs2(1,1);
	for(int i=1;i<=q;++i) if(op[i]==2) {
		int l=ql[i],r=qr[i];
		F[i]>>=l,F[i]<<=(MAXN-(r-l+1));
		int s=F[i].count();
		cout<<(1ll*s*(X-1)+r-l+1)%Y<<"\n";
	}
	return 0;
}