#include <bits/stdc++.h>
using namespace std;

using ui = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(l);i>=(r);--i)
#define repn(i,n) for(int i=0;i<(n);++i)
#define sizc(x) ((int)(x).size())
#define allc(x) (x).begin(),(x).end()
#define fir first
#define sec second

constexpr int N = 8e4+5, B = 300;

int n,m;
vector<int> G[N];

namespace Sieve{
    bitset<N> vis;
    vector<int> primes;
    void init(){
        rep(i,2,n)if(!vis[i]){
            primes.push_back(i);
            rep(j,2,n/i)vis[i*j]=1;
        }
    }
}
using Sieve::primes;

bitset<N> D[N],S,z,Z;
int g[N];

int f[N];
void dfs(int u,int fa){
    f[u]=fa;
    for(auto v:G[u])if(v!=fa)dfs(v,u);
}
vector<pair<int,int>> Q1[B],Q2[B];

vector<int> Q3[N];
pair<int,int> rg[N];

void dfsu(int x,int val){
    if(x==primes.size()||(ll)val*primes[x]>n){
        for(auto id:Q3[val])D[id]&=Z;
        return;
    }
    dfsu(x+1,val);
    int mul=1;
    while((ll)val*primes[x]<=n){
        val*=primes[x];
        mul*=primes[x];
        for(int i=mul;i<=n;i+=mul){
            g[i]*=primes[x];
            Z[i]=z[g[i]];
        }
        dfsu(x+1,val);
    }
    for(int i=primes[x];i<=n;i+=primes[x]){
        while(g[i]%primes[x]==0)g[i]/=primes[x];
        Z[i]=z[g[i]];
    }
}

signed main(){
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

    cin>>n>>m;
    rep(i,1,n){
        int x;cin>>x;
        z[i]=x&1;
    }
    rep(i,2,n){
        int u,v;cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    Sieve::init();
    rep(i,1,m){
        int op,l,r;
        cin>>op>>l>>r;
        if(op==1){
            int bl=(l-1)/B+1,br=(r-1)/B+1;
            if(bl==br){
                dfs(l,0),D[i][l]=1;
                rep(j,l+1,r){
                    int p=j;
                    while(!D[i][p])D[i][p]=1,p=f[p];
                }
                continue;
            }
            Q1[bl].emplace_back(l,i);
            Q2[bl].emplace_back(r,i);
        }
        else{
            int u;cin>>u;
            rg[i]={l,r};
            Q3[u].push_back(i);
        }
    }
    rep(i,1,(n-1)/B){
        int u=i*B;
        dfs(u,0);
        S.reset(),S[u]=1;
        int it=u;
        sort(allc(Q1[i]),greater<pair<int,int>>());
        sort(allc(Q2[i]));
        for(auto p:Q1[i]){
            while(it>p.fir){
                --it;
                int x=it;
                while(!S[x])S[x]=1,x=f[x];
            }
            D[p.sec]=S;
        }
        S.reset(),S[u]=1;
        it=u;
        for(auto p:Q2[i]){
            while(it<p.fir){
                ++it;
                int x=it;
                while(!S[x])S[x]=1,x=f[x];
            }
            D[p.sec]|=S;
        }
    }
    rep(i,1,m)D[i]^=D[i-1];
    rep(i,1,n)Z[i]=z[g[i]=1];
    dfsu(0,1);
    rep(i,1,m)if(rg[i].fir){
        int l,r;tie(l,r)=rg[i];
        D[i]>>=l;
        int s=D[i].count()-(D[i]>>r-l+1).count();
        cout<<(r-l+1+19901990ll*s)%20242024<<'\n';
    }
}