Cho một cây vô hướng ~n~ đỉnh với gốc là ~1~, mỗi đỉnh ~u~ có một giá trị là ~c[u]~. Cho ~q~ truy vấn có dạng như sau:

• Truy vấn có dạng "~1~ ~v~". Với truy vấn này, tạm gọi dãy ~u_1, u_2, ..., u_k~ là dãy đỉnh trong đường đi ngắn nhất từ đỉnh ~1~ tới đỉnh ~v~, (~u_k = v~). Bạn cần tìm một đỉnh ~u_i~ nào đó thỏa mãn ~gcd(c[u_i], c[v]) > 1~ với ~1 \le i < k~. Nếu có nhiều giá trị ~u_i~ thỏa mãn, hãy chọn đỉnh có ~i~ lớn nhất, ngược lại, in ra ~-1~ nếu không có đỉnh nào như vậy.
• Truy vấn có dạng "~2~ ~v~ ~w~". Với truy vấn này, bạn hãy đổi giá trị ~c[v] = w~. Có tối đa ~50~ truy vấn dạng này.

Hãy giải quyết bài toán trên.

Input

• Dòng đầu gồm ~2~ số nguyên dương ~n~ và ~q~ ~(1 \le n,q \le 10^5)~
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~c_1, c_2, ..., c_n~. ~(c_i \le 2*10^6)~
• ~n-1~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên dương ~u v~ miêu tả cạnh nối giữa hai đỉnh này.
• ~q~ dòng tiếp theo, mỗi dòng miêu tả một truy vấn. Lưu ý rằng, với mọi truy vấn, ~v \le n~, ~w \le 2*10^6~

Output

• In ra kết quả của các truy vấn dạng ~1~ thành từng dòng.

Sample Test

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