#include<iostream>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cmath>
#define N 1000
#define M 1000
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 gcd(int x,int y)
{
	if (!y) return x;
	return gcd(y,x%y);
}
int n,q,sl,sr,leng,block[N+1],w[N+1],depth[N+1],ans[N+1],lg[N+1],st[N+1],tong[N+1],length,op[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][N+1];
bitset<M+1>rst;
void add(int x,int y)
{
	E[x].push_back(y),E[y].push_back(x);
	return;
}
void dfs(int rt,int x)
{
	used[x]=1,B[rt][x][x]=1;
	for (int i=0;i<E[x].size();++i)
		if (!used[E[x][i]])
		    B[rt][E[x][i]]=B[rt][x],dfs(rt,E[x][i]);
	return;
}
int main()
{
	int x,y,szt,cnt;
	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);
	for (int i=1;i<=n;++i)
	{
		for (int j=1;j<=n;++j) used[j]=0;
		dfs(i,i);
	}
	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=1;i<=q;++i)
	{
		op[i]=read();
		if (op[i]==1)
		{
			l[i]=read(),r[i]=read(),rst.reset();
			if (l[i]==r[i]) rst[l[i]]=1;
			else
			{
				for (int j=l[i];j<=r[i]-1;++j) rst|=B[j][j+1];
			}
			for (int j=1;j<=n;++j) w[j]^=rst[j];
		}
		else
		{
			l[i]=read(),r[i]=read(),u[i]=read(),cnt=0;
			for (int j=l[i];j<=r[i];++j) cnt+=(z[gcd(u[i],j)]&w[j]);
			printf("%lld\n",(19901990ll*cnt+r[i]-l[i]+1)%20242024);
		}
	}
	return 0;
}