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.

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

Ràng buộc:

- 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