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 \leq i \leq N, 1 \leq X \leq 106).
• Loại 2 có dạng 2 i: Tìm giá trị S_i (1 \leq i \leq N)

• Dòng đầu chứa hai số nguyên dương là N và Q (N \leq 10^6, Q \leq 2 \times 10^5).
• Dòng thứ hai chứa N số nguyên là dãy A (1 \leq A_i \leq 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.

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.

• 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.