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}~ ~(1 \le i < N)~ thì hai phần tử này thuộc cùng một vùng. Như vậy dãy được chia thành các vùng là các đoạn liên tiếp, mỗi phần tử thuộc đúng một vùng. 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 \le i \le N,\ 1 \le X \le 10^6)~.

• Loại 2 có dạng ~2 i~: Tìm giá trị ~S_i~ ~(1 \le i \le N)~.

Dữ liệu

• Dòng đầu chứa hai số nguyên dương là ~N~ và ~Q~ ~(N \le 10^6,\ Q \le 2 \cdot 10^5)~.

• Dòng thứ hai chứa ~N~ số nguyên là dãy ~A~ ~(1 \le A_i \le 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

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

Sample Output

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.