#include<bits/stdc++.h>
using namespace std;
inline int qread()
{
	int a=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){(a*=10)+=(ch^48);ch=getchar();}
	return a*f;
}
int n,m,a[80010],OP[80010],L[80010],R[80010],vis[80010];
int cl,c[80010],ed[80010];
int dep[80010],fa[80010],st[17][80010],F[17][80010],ST[17][80010];
int gcd[80010],P,pri[80010];
vector<int>e[80010],Q[80010],Qs[80010];
vector< pair<int,int> >pre[80010],suf[80010];
bitset<80001>S[80001],cx,Z;
inline int cmp(int x,int y){return dep[x]<dep[y]?x:y;}
inline void U(int x,int p)
{
	if(x==1)return ;
	for(int i=x;i<=n;i+=x)Z[i]=a[gcd[i]*=p]&1;
	return ;
}
inline void M(int x,int p)
{ 
	if(x==1)return ;
	for(int i=x;i<=n;i+=x)Z[i]=a[gcd[i]/=p]&1;
	return ;
}
inline void dfs(int x,int h)
{
	if(!vis[x])
	{
		for(int i:Qs[x])S[i]=Z;
		vis[x]=1;
	}
	if(h==P+1)return ;
	if(1ll*x*pri[h]>n)return ;
	for(long long y=1;1ll*x*y<=n;y*=pri[h])
	{
		U(y,pri[h]);
		dfs(x*y,h+1);
	}
	for(long long y=1;1ll*x*y<=n;y*=pri[h])M(y,pri[h]);
	return ;
}
inline void dfss(int rt,int da)
{
	dep[rt]=dep[da]+1;
	st[0][rt]=rt;fa[rt]=da;
	F[0][rt]=da;ST[0][rt]=rt;
	for(int i=1;i<=16;++i)F[i][rt]=F[i-1][F[i-1][rt]];
	for(int i:e[rt])
	{
		if(i==da)continue;
		dfss(i,rt);
	}
	return ;
}
inline int get_lca(int x,int y)
{
	if(!x||!y)return x|y;
	if(dep[x]<dep[y])swap(x,y);
	for(int i=16;~i;--i)while(dep[F[i][x]]>=dep[y])x=F[i][x];
	if(x==y)return x;
	for(int i=16;~i;--i)while(F[i][x]^F[i][y])x=F[i][x],y=F[i][y];
	return F[0][x];
}
inline void dfsss(int rt,int da)
{
	cx.set(rt);
	for(int i:Q[rt])S[i]=S[i]^cx;
	for(int i:e[rt])
	{
		if(i==da)continue;
		dfsss(i,rt);
	}
	cx.reset(rt);
	return ;
}
inline int get_min(int l,int r)
{
	int s=31-__builtin_clz(r-l+1);
	return cmp(st[s][l],st[s][r-(1<<s)+1]);
}
inline int get_range_lca(int l,int r)
{
	int s=31-__builtin_clz(r-l+1);
	return get_lca(ST[s][l],ST[s][r-(1<<s)+1]);
}
signed main()
{
	n=qread(),m=qread();
	cl=min(n,(int)sqrt(n)+1);
//	cl=n;
	for(int i=1;i<=n;++i)a[i]=qread(),ed[c[i]=(i-1)/cl+1]=i;
	for(int i=1,u,v;i<n;++i)
	{
		u=qread(),v=qread();
		e[u].emplace_back(v);
		e[v].emplace_back(u);
	}
	dfss(1,0);
	for(int i=1;i<=16;++i)for(int j=1;j+(1<<i)-1<=n;++j)
	{
		st[i][j]=cmp(st[i-1][j],st[i-1][j+(1<<(i-1))]);
		ST[i][j]=get_lca(ST[i-1][j],ST[i-1][j+(1<<(i-1))]);
	}
	for(int i=1;i<=m;++i)
	{
		OP[i]=qread();L[i]=qread();R[i]=qread();
		if(OP[i]==2)Qs[qread()].emplace_back(i);
		else
		{
			Q[get_lca(L[i],R[i])].emplace_back(i);
			if(c[L[i]]==c[R[i]])
			{
				cx.reset();
				for(int j=L[i],p;j<=R[i];++j)
				{
					p=j;
					while(!cx[p])cx.set(p),p=fa[p];
				}
				S[i]=cx;
			}
			else
			{
				pre[ed[c[L[i]]]].emplace_back(make_pair(L[i],i));
				suf[ed[c[L[i]]]].emplace_back(make_pair(R[i],i));
			}
		}
	}
	for(int I=1,i,lp,p;I<=c[n];++I)
	{
		i=ed[I];
		sort(pre[i].begin(),pre[i].end());
		sort(suf[i].begin(),suf[i].end());
		reverse(pre[i].begin(),pre[i].end());
		cx.reset();lp=p=i;
		while(!cx[p])cx.set(p),p=fa[p];
		for(pair<int,int>j:pre[i])
		{
			if(lp>j.first)
			{
				while(lp>j.first)
				{
					p=--lp;
					while(!cx[p])cx.set(p),p=fa[p];
				}
			}
			S[j.second]=S[j.second]|cx;
		}
		cx.reset();lp=p=i;
		while(!cx[p])cx.set(p),p=fa[p];
		for(pair<int,int>j:suf[i])
		{
			if(lp<j.first)
			{
				while(lp<j.first)
				{
					p=++lp;
					while(!cx[p])cx.set(p),p=fa[p];
				}
			}
			S[j.second]=S[j.second]|cx;
		}
	}
	cx.reset();
	dfsss(1,0);
	for(int i=2;i<=n;++i)
	{
		if(!vis[i])pri[++P]=i;
		for(int j=1;j<=P&&pri[j]*i<=n;++j)
		{
			vis[pri[j]*i]=1;
			if(i%pri[j]==0)break;
		}
	}
	for(int i=1;i<=n;++i)Z[i]=a[1]&1,vis[i]=0;
	dfs(1,1);
	cx.reset();
	for(int i=1,x;i<=m;++i)
	{
//		for(int j=1;j<=n;++j)cerr<<S[i][j];puts("");
		if(OP[i]==1)cx^=S[i];
		else 
		{
			x=(((cx&S[i])>>(L[i]-1))<<(80000-R[i]+L[i]-1)).count();
			printf("%lld\n",(1ll*19901991*x+(R[i]-L[i]+1-x))%20242024);
		}
	} 
	return 0;
}