【原题】

Caisa is now at home and his son has a simple task for him.

Given a rooted tree with n vertices, numbered from 1 to n (vertex 1 is the root). Each vertex of the tree has a value. You should answer q queries. Each query is one of the following:

• Format of the query is "1 v". Let's write out the sequence of vertices along the path from the root to vertex v: u1,?u2,?...,?uk (u1?=?1; uk?=?v). You need to output such a vertex ui that gcd(value of ui,?value of v)?>?1 and i? k. If there are several possible vertices ui pick the one with maximum value of i. If there is no such vertex output -1.
• Format of the query is "2 v w". You must change the value of vertex v to w.

  You are given all the queries, help Caisa to solve the problem.

  Input

  The first line contains two space-separated integers n, q (1?≤?n,?q?≤?105).

  The second line contains n integers a1,?a2,?...,?an (1?≤?ai?≤?2?106), where ai represent the value of node i.

  Each of the next n?-?1 lines contains two integers xi and yi (1?≤?xi,?yi?≤?n; xi?≠?yi), denoting the edge of the tree between vertices xi and yi.

  Each of the next q lines contains a query in the format that is given above. For each query the following inequalities hold: 1?≤?v?≤?n and 1?≤?w?≤?2?106. Note that: there are no more than 50 queries that changes the value of a vertex.

  Output

  For each query of the first type output the result of the query.

  Sample test(s) input

  4 6
  10 8 4 3
  1 2
  2 3
  3 4
  1 1
  1 2
  1 3
  1 4
  2 1 9
  1 4
  

  output

  -1
  1
  2
  -1
  1
  

  Note

  gcd(x,?y) is greatest common divisor of two integers x and y.

  
  

  【分析】这道题是做现场赛的。本来能A的，但是太紧张了=而且也不会用vector，边表搞的麻烦死了。

  开始看到修改操作才50次、时间又松，真是爽！估计每次可以暴力重构这颗树，然后对于每个质因子记录最优值。

  首先每次不能sqrt的效率枚举一个数的因子，我们可以预处理出每个数的所有质因子。（其实有更省空间的）

  剩下来要解决的问题是：因为我是用dfs的，怎么把某个子树的信息在搜完后再去掉？（以免影响其他子树）HHD表示用vector一点也不虚。其实应该也可以用边表类似的思路，但是麻烦= =

  【代码】

  #include
      
       
  #include
       
         #include
        
          #include
         
           #define N 100005 #define S 2000005 #define push push_back #define pop pop_back using namespace std; vector
          
           fac[S],f[S]; int data[N],ans[N],end[N],pf[S],deep[N]; int C,cnt,n,Q,i,x,y,opt; struct arr{int go,next;}a[N*2]; inline void add(int u,int v){a[++cnt].go=v;a[cnt].next=end[u];end[u]=cnt;} inline void init() { int H=2000000; for (int i=2;i<=H;i++) if (!pf[i]) { for (int j=i;j<=H;j+=i) fac[j].push(i),pf[j]=1; } } void dfs(int k,int fa) { int P=data[k]; for (int i=0;i
           
            deep[ans[k]]) ans[k]=f[go][temp-1]; f[go].push(k); } for (int i=end[k];i;i=a[i].next) if (a[i].go!=fa) dfs(a[i].go,k); for (int i=0;i