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}~ ~(\forall \; 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 \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)~.

Input

• Dòng đầu chứa hai số nguyên dương ~N~ và ~Q~ ~(N \le 10^6,~ ~Q \le 2 \times 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.

Output

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

Samples

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

Scoring

• 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