Cho một dãy số nguyên ~A~ gồm ~N~ phần tử, các phần tử được đánh số từ ~1~ đến ~N~ .

Nếu phần tử ~A_i~ là ước của phần tử ~A_{i+1}(∀i < n)~ thì hai phần tử này thuộc cùng một vùng. Dễ nhận thấy rằng mỗi phần tử chỉ thuộc vào một vùng duy nhất. Gọi ~S_i~ là chỉ số nhỏ nhất của các phần tử cùng chung một vùng với phần tử ~A_i~.

Yêu cầu thực hiện ~Q~ truy vấn thuộc một trong hai loại:

• Loại 1 có dạng ~1\ i\ X~: Đổi giá trị ~A_i~ thành ~X~ ~(1 ≤ i ≤ N, 1 ≤ X ≤ 10^6)~.
• Loại 2 có dạng ~2\ i~: Tìm giá trị ~S_i\ (1 ≤ i ≤ N)~.

Dữ liệu

• Dòng đầu chứa hai số nguyên dương là ~N~ và ~Q~ ~(N ≤ 10^6, Q ≤ 2 · 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên là dãy ~A~ ~(1 ≤ A_i ≤ 10^6)~.
• Mỗi dòng trong ~Q~ dòng tiếp theo là một truy vấn thuộc một trong hai loại trên.

Kết quả

• Với mỗi truy vấn loại 2, in một dòng chứa một số nguyên duy nhất là kết quả của truy vấn.

Ví dụ

Sample Input 1

5 5
2 2 7 14 14
1 1 3
1 2 6
2 2
2 4
2 5

Sample Output 1

1
3
3

Chấm điểm

• Subtask 1 (60% số test): Độ dài của một vùng bất kì luôn nhỏ hơn 100.
• Subtask 2 (40% số test): Không có ràng buộc gì thêm.

Nguồn: Beginner Free Contest 30