#include <bits/stdc++.h>
using namespace std;
bool deb = false;
const int N = 2000011;
vector<int> gr[100011];
int a[100011], ans[100011], dep[100011], idep[100011];
bool prime[N];
int spf[N];
stack<int> s[200011];
int Index[N];
void sieve() {
  int i, j = 0;
  for (i = 2; i < N - 5; i++) {
    if (prime[i] != 1) {
      for (j = 2; i * j < N - 5; j++) {
        if (spf[i * j] == 0) spf[i * j] = i;
        prime[i * j] = 1;
      }
    }
  }
  j = 0;
  for (i = 2; i < N - 5; ++i)
    if (prime[i] != 1) {
      spf[i] = i;
      Index[i] = j++;
    }
  prime[1] = 1;
}
void dfs(int v, int pa) {
  int i;
  int p = a[v];
  dep[v] = dep[pa] + 1;
  idep[dep[v]] = v;
  set<int> st;
  while (spf[p] != 0) {
    st.insert(spf[p]);
    p /= spf[p];
  }
  auto it = st.begin();
  vector<int> fact;
  for (it = (st).begin(); it != (st).end(); ++it) {
    fact.push_back(*it);
  }
  int mx = 0, node = v;
  for (i = 0; i < (int)fact.size(); ++i) {
    if (s[Index[fact[i]]].empty()) continue;
    if (dep[s[Index[fact[i]]].top()] >= mx) {
      mx = dep[s[Index[fact[i]]].top()];
      node = idep[dep[s[Index[fact[i]]].top()]];
    }
  }
  ans[v] = node;
  for (i = 0; i < (int)fact.size(); ++i) s[Index[fact[i]]].push(v);
  for (i = 0; i < (int)gr[v].size(); ++i) {
    int u = gr[v][i];
    if (u != pa) {
      dfs(u, v);
    }
  }
  for (i = 0; i < (int)fact.size(); ++i) {
    s[Index[fact[i]]].pop();
  }
}
int main() {
  int i, j, n, q;
  sieve();
  scanf("%d", &n), scanf("%d", &q);
  for (i = 1; i < n + 1; ++i) scanf("%d", &a[i]);
  for (i = 1; i < n; ++i) {
    int u, v;
    scanf("%d", &u), scanf("%d", &v);
    gr[u].push_back(v);
    gr[v].push_back(u);
  }
  dfs(1, 0);
  while (q--) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int u;
      scanf("%d", &u);
      if (ans[u] == u)
        printf("%d\n", -1);
      else
        printf("%d\n", ans[u]);
    } else {
      int u, v;
      scanf("%d", &u), scanf("%d", &v);
      a[u] = v;
      dfs(1, 0);
    }
  }
  return 0;
}
