Cho mảng \(A\) gồm \(N\) số nguyên dương. Hãy thực hiện hai loại truy vấn sau trên mảng:

• 1 pos val: Cập nhật \(A[pos] = val\).
• 2 l r: Tính ước chung lớn nhất (UCLN) của tất cả các phần tử trong khoảng từ \(l\) đến \(r\) (tức là \(\gcd(a_l, a_{l+1}, \dots, a_r)\)).

Định dạng đầu vào

• Dòng đầu chứa \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng hai chứa \(N\) số nguyên dương \(a_i\) (\(1 \le a_i \le 10^9\)).
• \(Q\) dòng tiếp theo chứa các truy vấn.

Định dạng đầu ra

• In ra kết quả UCLN cho mỗi truy vấn loại 2.

Ví dụ

Input:

5 3
12 18 24 8 16
2 1 3
1 4 12
2 3 5

Output:

6
4