#include<iostream>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cmath>
#define N 80000
#define M 512
using namespace std;
const int sz=512;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int n,q,sl,sr,leng,block[N+1],depth[N+1],ans[N+1],lg[N+1],st[N+1],tong[N+1],length,op[N+1],lc[N+1],l[N+1],r[N+1],u[N+1],fa[N+1][21];
bool z[N+1],nprime[N+1],used[N+1];
vector<int>E[N+1];
vector<int>p[N+1];
bitset<M+1>B[N+1];
bitset<M+1>S[N+1];
bitset<M+1>rst;
bitset<M+1>dst;
bitset<M+1>DP[M+1][M+1];
bitset<M+1>delta[N+1];
bitset<M+1>delta2[N+1];
bitset<M+1>num[N+1];
void add(int x,int y)
{
	E[x].push_back(y),E[y].push_back(x);
	return;
}
void dfs(int x)
{
	st[++leng]=x,used[x]=1;
	for (int i=0;i<E[x].size();++i)
		if (!used[E[x][i]])
			depth[E[x][i]]=depth[x]+1,fa[E[x][i]][0]=x,dfs(E[x][i]);
	return;
}
int lca(int x,int y)
{
	if (depth[x]<depth[y]) swap(x,y);
	for (int i=lg[n];i>=0;--i)
		if (depth[fa[x][i]]>=depth[y])
			x=fa[x][i];
	if (x==y) return x;
	for (int i=lg[n];i>=0;--i)
		if (fa[x][i]!=fa[y][i])
			x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
bitset<M+1>query(int l,int r)
{
	if (l<=sl&&sr<=r) return dst;
	else if (l==r)
	{
		bitset<M+1>res;
		if (sl<=l&&l<=sr) res[l-sl]=1;
		return res;
	}
	else if (block[l+1]==block[r])
	{
		bitset<M+1>res;
		for (int i=l+1;i<=r;++i) res|=S[i];
		return res;
	}
	else if (block[l+1]+1==block[r]) return delta[l+1]|delta2[r];
	else return delta[l+1]|DP[block[l+1]+1][block[r]-1]|delta2[r];
}
int main()
{
	int x,y,szt;
	n=read(),q=read(),szt=sqrt(n);
	for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
	for (int i=1;i<=n;++i) z[i]=read()&1,block[i]=(i-1)/szt+1;
	for (int i=1;i<=n-1;++i) x=read(),y=read(),add(x,y);
	depth[1]=1,dfs(1);
	for (int i=1;i<=lg[n];++i)
		for (int j=1;j<=n;++j)
			fa[j][i]=fa[fa[j][i-1]][i-1];
	for (int i=2;i<=n;++i) lc[i]=lca(i-1,i);
	for (int i=1;i<=q;++i)
	{
		op[i]=read();
		if (op[i]==1) l[i]=read(),r[i]=read();
		else l[i]=read(),r[i]=read(),u[i]=read();
	}
	for (int i=1;i<=n;++i)
		for (int j=i;j<=n;j+=i)
			p[j].push_back(i);
	for (int i=2;i<=n;++i)
		if (!nprime[i])
		{
			tong[++length]=i;
			for (int j=(i<<1);j<=n;j+=i) nprime[j]=1;
		}
	for (int i=1;i<=n;++i)
		for (int j=(i<<1);j<=n;j+=i)
			z[j]^=z[i];
	for (int i=1;i<=n;i+=sz)
	{
		sl=i,sr=min(i+sz-1,n),rst.reset(),dst.reset();
		for (int j=sl;j<=sr;++j) dst[j-sl]=1;
		for (int j=1;j<=n;++j) B[j].reset();
		for (int j=1;j<=block[n];++j)
			for (int k=1;k<=block[n];++k)
				DP[j][k].reset();
		for (int j=sl;j<=sr;++j)
			for (int k=0;k<p[j].size();++k)
				if (z[p[j][k]])
					B[p[j][k]][j-sl]=1;
		for (int j=1;j<=length;++j)
			for (int k=1;k<=n/tong[j];++k)
				B[k*tong[j]]^=B[k];
		for (int j=1;j<=n;++j)
		{
			S[j]=S[fa[j][0]];
			if (sl<=j&&j<=sr) S[j][j-sl]=1;
		}
		for (int j=n;j>=2;--j) S[j]^=S[j-1];
		for (int j=2;j<=n;++j)
			if (sl<=lc[j]&&lc[j]<=sr)
				S[j][lc[j]-sl]=1;
		for (int j=1;j<=n;++j) delta[j]=delta2[j]=S[j],DP[block[j]][block[j]]=DP[block[j]][block[j]]|S[j];
		for (int j=n-1;j>=1;--j)
			if (block[j]==block[j+1])
				delta[j]|=delta[j+1];
		for (int j=2;j<=n;++j)
			if (block[j]==block[j-1])
				delta2[j]|=delta2[j-1];
		for (int j=1;j<=block[n];++j)
			for (int k=j+1;k<=block[n];++k)
				DP[j][k]=DP[j][k-1]|DP[k][k];
		num[sl-1].reset();
		for (int j=sl;j<=sr;++j) num[j]=num[j-1],num[j][j-sl]=1;
		for (int j=1;j<=q;++j)
		{
			if (op[j]==1) rst^=query(l[j],r[j]);
			else if (l[j]<=sl&&sr<=r[j]) ans[j]+=(B[u[j]]&rst).count();
			else if (max(l[j],sl)<=min(r[j],sr)) ans[j]+=(B[u[j]]&rst&(num[min(r[j],sr)]^num[max(l[j],sl)-1])).count();
		}
	}
	for (int i=1;i<=q;++i)
		if (op[i]==2)
			printf("%lld\n",(19901990ll*ans[i]+r[i]-l[i]+1)%20242024);
	return 0;
}