#include <bits/stdc++.h>

using namespace std;

// #define LOCK_GETCHAR
// #define USE_INT_128

#if __cplusplus < 201400
#warning "Please use c++14 or higher."
#define CONSTEXPR_FUNC
#define ENABLE_IF_INT
#else
#define CONSTEXPR_FUNC constexpr
#define ENABLE_IF_INT , enable_if_t<_is_integer<T>, int> = 0
template <class T> constexpr bool _is_integer = numeric_limits<T>::is_integer;
template <> constexpr bool _is_integer<bool> = false;
template <> constexpr bool _is_integer<char> = false;
#ifdef USE_INT_128
template <> constexpr bool _is_integer<__int128> = true;
template <> constexpr bool _is_integer<__uint128_t> = true;
#endif
template <class T ENABLE_IF_INT>
constexpr T INF = numeric_limits<T>::max() >> 1;
#endif

#if !defined(_WIN32) && !defined(LOCK_GETCHAR)
#define getchar getchar_unlocked
#endif

#define il inline
#define mkp make_pair
#define fi first
#define se second
#define For(i, j, k) for (decltype(j - k) i = (j); i <= (k); ++i)     // NOLINT
#define ForDown(i, j, k) for (decltype(j - k) i = (j); i >= (k); --i) // NOLINT
#define pb push_back
#define eb emplace_back
#ifndef ONLINE_JUDGE
#define FileIO(filename)                                                       \
  freopen(filename ".in", "r", stdin);                                         \
  freopen(filename ".out", "w", stdout)
#else
#define FileIO(filename) void(0)
#endif

using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using db = double;
using ldb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#ifdef USE_INT_128
using lll = __int128_t;
using ulll = __uint128_t;
#endif

// clang-format off
template<typename T> constexpr il T sq(const T & x){ return x * x; }
template<typename T> CONSTEXPR_FUNC il void cmin(T & x, const T &y){ x = min(x, y); }
template<typename T> CONSTEXPR_FUNC il void cmax(T & x, const T &y){ x = max(x, y);}
template<typename T> CONSTEXPR_FUNC il T qpow(T x, ull y, T mod){T ans = 1; x %= mod; while (y) { if(y & 1)(ans *= x) %= mod;(x *= x) %= mod; y >>= 1;} return ans;}
template<typename T> CONSTEXPR_FUNC il T qpow(T x, ull y){T ans = 1; while (y) {if(y & 1) ans *= x;x *= x;y >>= 1;} return ans;}
template<typename T ENABLE_IF_INT> il void read(T &x){ x = 0; int f = 1; int c = getchar(); while(!isdigit(c)) {if (c == '-') f = -1;c = getchar();} while(isdigit(c)) {x = x * 10 + c - '0';c = getchar();} x *= f;}
template<typename T, typename ... Args> il void read(T &x, Args &... y){ read(x); read(y...); }
// clang-format on

// File head end

namespace {
constexpr ll MAXN = 80005;
int n, q, B, Z[MAXN], fa[MAXN], dep[MAXN], sz[MAXN], seq[18][MAXN],
    lca[18][MAXN], dfn[MAXN], d_gcd[MAXN], cnt = 0;
ll Ans[MAXN];
vector<int> T[MAXN], brute, top[MAXN], prime, todo[MAXN];
vector<pii> Q_pre[MAXN], Q_nxt[MAXN];
tuple<int, int, int, int> qry[MAXN];
bitset<MAXN> Val[MAXN], W[MAXN], F, All, notPrime;
void dfs1(int x, int pre) {
  fa[x] = pre, dep[x] = dep[pre] + 1, sz[x] = 1, seq[0][dfn[x] = ++cnt] = x;
  for (int v : T[x])
    if (v != pre) {
      dfs1(v, x);
      sz[x] += sz[v];
    }
}
il void sieve() {
  notPrime[1] = 1;
  For(i, 2, n) {
    if (!notPrime[i])
      prime.eb(i);
    for (int j : prime) {
      if (1ll * i * j > n)
        break;
      notPrime[i * j] = 1;
      if (!(i % j))
        break;
    }
  }
}
il void init_st1() {
  For(i, 1, 17) For(j, 1, n - (1 << i) + 1) {
    int u = seq[i - 1][j], v = seq[i - 1][j + (1 << i - 1)];
    seq[i][j] = dep[u] < dep[v] ? u : v;
  }
}
il int LCA1(int u, int v) {
  auto qry_st1 = [&](int l, int r) {
    assert(l <= r);
    int f = __lg(r - l + 1), u = seq[f][l], v = seq[f][r - (1 << f) + 1];
    return dep[u] < dep[v] ? u : v;
  };
  if (u == v)
    return u;
  else if (dfn[u] > dfn[v])
    swap(u, v);
  return fa[qry_st1(dfn[u] + 1, dfn[v])];
}
il void init_st2() {
  iota(lca[0] + 1, lca[0] + 1 + n, 1);
  For(i, 1, 17) For(j, 1, n - (1 << i) + 1) lca[i][j] =
      LCA1(lca[i - 1][j], lca[i - 1][j + (1 << i - 1)]);
}
il int LCA2(int l, int r) {
  int f = __lg(r - l + 1);
  return LCA1(lca[f][l], lca[f][r - (1 << f) + 1]);
}
il void mark(int id, int l, int r) {
  top[LCA2(l, r)].eb(id);
  if (l / B == r / B)
    return brute.eb(id), void();
  Q_nxt[r / B].eb(r, id);
  Q_pre[r / B].eb(l, id);
}
void dfs2(int x) {
  static bitset<MAXN> cur;
  for (int id : top[x])
    Val[id] ^= cur;
  cur[x] = 1;
  for (int v : T[x])
    if (v != fa[x])
      dfs2(v);
  cur[x] = 0;
}

void dynamic_gcd(int num, int P) {
  if (num >= prime.size() || 1ll * P * prime[num] > n) {
    for (int id : todo[P]) {
      int l, r, c;
      tie(ignore, l, r, ignore) = qry[id];
      auto qwq = (F & W[id]);
      (qwq >>= (l - 1)) &= (All >> (n - (r - l + 1)));
      qwq[0] = 0, c = qwq.count();
      Ans[id] = (19901991ll * c + (r - l + 1 - c)) % 20242024ll;
    }
    return;
  }
  dynamic_gcd(num + 1, P);
  for (ll pw = prime[num]; pw * P <= n; pw *= prime[num]) {
    for (int id = pw; id <= n; id += pw) {
      d_gcd[id] *= prime[num];
      F[id] = Z[d_gcd[id]] & 1;
    }
    dynamic_gcd(num + 1, P * pw);
  }
  for (int id = prime[num]; id <= n; id += prime[num])
    while (!(d_gcd[id] % prime[num]))
      d_gcd[id] /= prime[num], F[id] = Z[d_gcd[id]] & 1;
}

il void Main() {
  read(n, q), B = max(1.0 * n / sqrt(q), 1.0), sieve();
  // cerr << B << '\n';
  For(i, 1, n) All[i] = 1;
  For(i, 1, n) read(Z[i]);
  For(i, 1, n - 1) {
    int u, v;
    read(u, v), T[u].eb(v), T[v].eb(u);
  }

  dfs1(1, 0);
  init_st1();
  init_st2();

  For(i, 1, q) {
    int op, x, y, z = 0;
    read(op, x, y);
    if (op == 2)
      read(z), todo[z].eb(i);
    else
      mark(i, x, y);
    qry[i] = {op, x, y, z};
  }

  for (int i = 0; i <= n / B; i++) {
    sort(Q_nxt[i].begin(), Q_nxt[i].end());
    sort(Q_pre[i].begin(), Q_pre[i].end());
    bitset<MAXN> cur;
    cur.reset();
    int id = 0;
    For(j, max(1, i * B), min((i + 1) * B - 1, n)) {
      int p = j;
      while (p && !cur[p])
        cur[p] = 1, p = fa[p];
      while (id < Q_nxt[i].size() && Q_nxt[i][id].fi == j)
        Val[Q_nxt[i][id++].se] |= cur;
    }
    cur.reset(), id = 0;
    ForDown(j, i * B - 1, 1) {
      int p = j;
      while (p && !cur[p])
        cur[p] = 1, p = fa[p];
      while (id < Q_pre[i].size() && Q_pre[i][id].fi == j)
        Val[Q_pre[i][id++].se] |= cur;
    }
  }
  for (int id : brute) {
    int l, r;
    bitset<MAXN> cur;
    tie(ignore, l, r, ignore) = qry[id];
    For(i, l, r) {
      int p = i;
      while (p && !cur[p])
        cur[p] = 1, p = fa[p];
    }
    Val[id] |= cur;
  }
  dfs2(1);
  bitset<MAXN> _W;
  For(i, 1, q) {
    int op, x, y, z;
    tie(op, x, y, z) = qry[i];
    if (op == 1)
      _W ^= Val[i];
    else
      W[i] = _W;
  }
  fill(d_gcd + 1, d_gcd + 1 + n, 1);
  For(i, 1, n) F[i] = Z[1] & 1;
  dynamic_gcd(0, 1);
  For(i, 1, q) if (get<0>(qry[i]) == 2) cout << Ans[i] << '\n';
}
} // namespace

signed main() { return Main(), 0; }