Cho một dãy A gồm N phần tử a₁, a₂,..a_N và Q truy vấn, mỗi truy vấn là một trong 2 loại sau:

- Loại 1 có dạng 1 u x: Giá trị phần tử thứ u được thay đổi về x (1 ≤ u ≤ N);

- Loại 2 có dạng 2 l r: Tính ước chung lớn nhất của các phần tử từ vị trí l đến vị trí r (1 ≤ l ≤ r ≤ N).

Yêu cầu: Hãy đưa ra câu trả lời cho mỗi truy vấn loại 2.

Dữ liệu vào: Có cấu trúc như sau:

- Dòng đầu tiên gồm 2 số nguyên N, Q (1 ≤ N, Q ≤ 10⁵);

- Dòng thứ hai chứa N số nguyên a₁, a₂,..., a_N miêu tả giá trị ban đầu của dãy (1 ≤ a_i ≤ 10⁹);

- Q dòng tiếp theo, mỗi dòng chứa 3 số nguyên miêu tả một trong 2 truy vấn đã được đề cập ở trên.

Kết quả: Ứng với mỗi truy vấn loại 2, in ra đáp án tìm được trên một dòng.