463_E. Caisa and Tree_34947
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.

Examples

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.
import java.io.*;
import java.util.*;
import java.math.BigInteger.*;
import static java.lang.Math.*;
import static java.math.BigInteger.*;
import static java.util.Arrays.*;
import java.util.logging.Level;
import java.util.logging.Logger;

// https://netbeans.org/kb/73/java/editor-codereference_ru.html#display
//<editor-fold defaultstate="collapsed" desc="Main">
public class Solution {

    private void run() {
//        Locale.setDefault(Locale.US);
        boolean oj = true;
        try {
            oj = System.getProperty("MYLOCAL") == null;
        } catch (Exception e) {
        }

        if (oj) {
            sc = new FastScanner(new InputStreamReader(System.in));
            out = new PrintWriter(new OutputStreamWriter(System.out));
        } else {
            try {
                sc = new FastScanner(new FileReader("input.txt"));
                out = new PrintWriter(new FileWriter("output.txt"));
            } catch (IOException e) {
                MLE();
            }
        }
        Solver s = new Solver();
        s.sc = sc;
        s.out = out;
        s.solve();
        if (!oj) {
            err.println("Time: " + (System.currentTimeMillis() - timeBegin) / 1e3);
            err.printf("Mem: %d\n", (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) >> 20);
        }
        out.flush();
    }

    private void show(int[] arr) {
        for (int v : arr) {
            err.print(" " + v);
        }
        err.println();
    }

    public static void exit() {
        err.println("Time: " + (System.currentTimeMillis() - timeBegin) / 1e3);
        out.flush();
        out.close();
        System.exit(0);
    }

    public static void MLE() {
        //for(;;);
        int[][] arr = new int[1024 * 1024][];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new int[1024 * 1024];
        }
    }

    public static void main(String[] args) {
        new Solution().run();
    }

    static long timeBegin = System.currentTimeMillis();
    static FastScanner sc;
    static PrintWriter out;
    static PrintStream err = System.err;
}
//</editor-fold>

//<editor-fold defaultstate="collapsed" desc="FastScanner">
class FastScanner {

    BufferedReader br;
    StringTokenizer st;

    FastScanner(InputStreamReader reader) {
        br = new BufferedReader(reader);
        st = new StringTokenizer("");
    }

    String next() {
        while (!st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException ex) {
                Solution.MLE();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }
}
//</editor-fold>


class Solver {

    FastScanner sc;
    PrintWriter out;
    PrintStream err = System.err;

    static ArrayList<Integer>[] prim;
    static {
        prim = new ArrayList[(int)2e6+1];
        for (int i = 0; i < prim.length; i++) {
            prim[i] = new ArrayList<>(7);
        }
        boolean[] isP = new boolean[prim.length];
        fill( isP, true );
        int cntPrimes = 0;
        for (int i = 2; i < isP.length; i++) {
            if( isP[i] ){
                ++cntPrimes;
                for (int j = i; j < isP.length; j +=i ) {
                    prim[j].add(i);
                    isP[j] = false;
                }
            }
        }
        System.err.println("cntPrimes: " + cntPrimes);
    }

    int n, q;
    int[] val;
    ArrayList<Integer>[] gr;
    int[] sz, goUp;
    
    void dfs( int v, int pr ){
        goUp[v] = pr;
        sz[v] = 1;
        for( int to : gr[v] ){
            if( to == pr ) continue;
            dfs( to, v );
            sz[v] += sz[to];
        }
    }

    boolean cross( ArrayList<Integer> aa, ArrayList<Integer> bb ){
        if( aa.size() > bb.size() )
            return cross(bb, aa);
        for( int a : aa )
            if( 0 <= Collections.binarySearch(bb, a) )
                    return true;
        return false;
    }
    
    void solve(){
        n = sc.nextInt();
        q = sc.nextInt();
        val = new int[n+1];
        for (int i = 1; i <= n; i++) {
            val[i] = sc.nextInt();
        }
        gr = new ArrayList[n+1];
        for (int v = 1; v <= n; v++){
            gr[v] = new ArrayList<>();
        }
        for (int it = 0; it < n-1; it++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            gr[a].add(b);
            gr[b].add(a);
        }
        
        sz = new int[n+1];
        goUp = new int[n+1];
        dfs(1, -1);

        
        cycMain:
        for (int iter = 0; iter < q; iter++) {
            int op = sc.nextInt();
            int v = sc.nextInt();
            if     ( op == 1 ){
                ArrayList<Integer> primList = prim[val[v]];
                v = goUp[v];
                while( 1 <= v ){
                    if( cross(primList, prim[val[v]]) ){
                        out.println( v );
                        continue cycMain;
                    }
                    v = goUp[v];
                }
                out.println( "-1" );
            }
            else if( op == 2 ){
                int w = sc.nextInt();
                val[v] = w;
            }
            else Solution.MLE();
        }
    }
    
}