#include <bits/stdc++.h>
using namespace std;
const int N = 8e4 + 3;
const int mod = 20242024;
const int A = 19901990;
const int M = 285;
const int B = 282;

inline int read() {
    char ch = getchar(); int x = 0;
    while (!isdigit(ch)) {ch = getchar();}
    while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
    return x;
}

struct node {
    int id, l, r;
}q[N];
int n, prime[10000], p[N], pw[N], cnt, fa[N], top[N], son[N], sz[N], T, depth[N], pre[N], suf[N], lca[M][M], Ans[N], pos[N];
int v[N][3];
short Gcd[M][M];
bitset<N> vis, a, mem[N];
vector<int> g[N];

inline int calc(int x, int y) {
    int ans = 1, res;
    for (int i = 0; i < 3; ++i) {
        if (v[x][i] <= B) res = Gcd[v[x][i]][y % v[x][i]];
        else if (y % v[x][i]) res = 1;
        else res = v[x][i];
        ans *= res; y /= res;
    }
    return ans;
}

void init() {
    n = read(); T = read();
    for (int i = 1; i <= n; ++i) a[i] = (read() & 1);
    v[1][0] = v[1][1] = v[1][2] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!vis[i]) {
            prime[++cnt] = i; pos[i] = cnt;
            p[i] = i; pw[i] = i;
            v[i][0] = i;
            v[i][1] = v[i][2] = 1;
        }
        for (int j = 1, k; j <= cnt && i * prime[j] <= n; ++j) {
            k = i * prime[j];
            vis[k] = 1;
            p[k] = p[i];
            v[k][0] = v[i][0];
            v[k][1] = v[i][1];
            v[k][2] = v[i][2];
            if (v[k][0] == 1 || v[k][0] * prime[j] <= B) v[k][0] *= prime[j];
            else if (v[k][1] == 1 || v[k][1] * prime[j] <= B) v[k][1] *= prime[j];
            else v[k][2] *= prime[j];
            if (p[i] == prime[j]) pw[k] = pw[i] * prime[j];
            else pw[k] = pw[i];
            if (i % prime[j] == 0) break;
        }
    }
    for (int i = 0; i <= B; ++i) {
        Gcd[i][0] = Gcd[0][i] = i;
        for (int j = 1; j <= i; ++j)
            Gcd[i][j] = Gcd[j][i] = Gcd[i % j][j];
    }
}

void dfs1(int x, int pa, int d) {
    fa[x] = pa; depth[x] = d; sz[x] = 1;
    for (auto y : g[x]) {
        if (y == pa) continue;
        dfs1(y, x, d + 1);
        sz[x] += sz[y];
        if (sz[y] > sz[son[x]]) son[x] = y;
    }
}

void dfs2(int x, int anc) {
    top[x] = anc;
    if (son[x]) dfs2(son[x], anc);
    for (auto y : g[x]) {
        if (y == fa[x] || y == son[x]) continue;
        dfs2(y, y);
    }
}

inline int LCA(int x, int y) {
    while (top[x] != top[y]) {
        if (depth[top[x]] < depth[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    if (depth[x] > depth[y]) swap(x, y);
    return x;
}

inline int get(int l, int r) {
    int posl = (l - 1) / B;
    int posr = (r - 1) / B;
    if (posl == posr) {
        int x = l;
        for (int i = l + 1; i <= r; ++i) x = LCA(x, i);
        return x;
    }else {
        int x = LCA(suf[l], pre[r]);
        if (posl + 1 < posr) x = LCA(x, lca[posl + 1][posr - 1]);
        return x;
    }
}

vector<int> vec, ex[N], val[N];
bitset<N> in, now, fin;

void dfs(int x) {
    now[x] = 1;
    for (auto id : ex[x]) mem[id] ^= now;
    for (auto y : g[x]) {
        if (y == fa[x]) continue;
        dfs(y);
    }
    now[x] = 0;
}

void work(int i) {
    fin = (now & mem[i]);
    fin >>= (q[i].l);
    fin <<= (q[i].l + N - q[i].r - 1);
    Ans[i] = 1ll * fin.count() * A % mod;
    Ans[i] = (Ans[i] + q[i].r - q[i].l + 1) % mod;
}

void dfs3(int x) {
    for (int i = pw[x]; i <= n; i += pw[x]) now[i] = a[calc(x, i)];
    for (auto i : val[x]) work(i);
    for (int i = pos[p[x]]; i <= cnt; ++i) {
        if (1ll * prime[i] * x > n) break;
        dfs3(prime[i] * x);
    }
    for (int i = pw[x]; i <= n; i += pw[x]) now[i] = a[calc(x / p[x], i)];
}

int main() {
    init();
    for (int i = 1, x, y; i < n; ++i) {
        x = read(); y = read();
        g[x].push_back(y); g[y].push_back(x);
    }
    dfs1(1, 1, 1); dfs2(1, 1);
    for (int i = 1; i <= n; ++i) {
        if (i % B == 1) pre[i] = i;
        else pre[i] = LCA(pre[i - 1], i);
    }
    for (int i = n; i >= 1; --i) {
        if (i == n || i % B == 0) suf[i] = i;
        else suf[i] = LCA(suf[i + 1], i);
    }
    for (int i = 1, o = 0; i <= n; i += B, ++o) lca[o][o] = suf[i];
    int mx = (n - 1) / B;
    for (int i = 0; i <= mx; ++i)
        for (int j = i + 1; j <= mx; ++j)
            lca[i][j] = LCA(lca[i][j - 1], lca[j][j]);
    for (int i = 1, opt; i <= T; ++i) {
        opt = read();
        if (opt == 1) {
            q[i].id = 0;
            q[i].l = read();
            q[i].r = read();
            int x = get(q[i].l, q[i].r);
            if (x != 1) ex[fa[x]].push_back(i);
        }else {
            q[i].l = read();
            q[i].r = read();
            q[i].id = read();
        }
    }
    for (int i = 1; i <= n; i += B) {
        for (int j = 1; j <= T; ++j) {
            if (q[j].id != 0) continue;
            if (in[j]) continue;
            if (q[j].r < i || q[j].l > i) continue;
            vec.push_back(j);
            in[j] = true;
        }
        if (vec.empty()) continue;
        sort(vec.begin(), vec.end(), [&](int x, int y) {return q[x].l > q[y].l;});
        int o = 0;
        for (int j = i, x; j >= 1; --j) {
            x = j;
            while (!now[x]) now[x] = true, x = fa[x];
            while (o < vec.size() && q[vec[o]].l == j) mem[vec[o]] |= now, o++;
        }
        now.reset(); o = 0;
        sort(vec.begin(), vec.end(), [&](int x, int y) {return q[x].r < q[y].r;});
        for (int j = i, x; j <= n; ++j) {
            x = j;
            while (!now[x]) now[x] = true, x = fa[x];
            while (o < vec.size() && q[vec[o]].r == j) mem[vec[o]] |= now, o++;
        }
        now.reset(); vec.clear();
    }
    for (int i = 1; i <= T; ++i) {
        if (q[i].id != 0) continue;
        if (in[i]) continue;
        for (int j = q[i].l, x; j <= q[i].r; ++j) {
            x = j;
            while (!now[x]) now[x] = true, x = fa[x];
        }
        mem[i] = now; now.reset();
    }
    dfs(1);
    for (int i = 1; i <= T; ++i) {
        mem[i] ^= mem[i - 1];
        if (q[i].id != 0) val[q[i].id].push_back(i);
    }
    now.reset();
    for (int i = 1; i <= n; ++i) now[i] = a[1];
    for (auto i : val[1]) work(i);
    for (int i = 1; i <= cnt; ++i) dfs3(prime[i]);
    for (int i = 1; i <= T; ++i)
        if (q[i].id != 0) printf("%d\n", Ans[i]);
    return 0;
}