#5212. RANGEGCD - Ước chung lớn nhất trên đoạn

Cho một dãy số nguyên dương gồm phần tử. Thực hiện thao tác, gồm hai loại:

1. update idx val: Thay đổi giá trị thành .
2. query L R: Tìm ước số chung lớn nhất (GCD) của tất cả các phần tử trong đoạn con .

Dữ liệu:

• Dòng đầu tiên gồm hai số nguyên và (, ) - số lượng phần tử và số lượng thao tác.
• Dòng thứ hai gồm số nguyên dương () - các phần tử của dãy.
• dòng tiếp theo, mỗi dòng mô tả một thao tác:
  • update idx val (, ).
  • query L R ().

Kết quả: Với mỗi thao tác query, in ra một dòng duy nhất chứa ước chung lớn nhất của các phần tử trong đoạn từ đến .

Ví dụ:

Dữ liệu:

5 5
12 18 24 30 36
query 1 3
update 2 27
query 2 4
update 4 42
query 1 5

Kết quả:

6
3
6

Giải thích:

• query 1 3: .
• update 2 27: được cập nhật thành 27.
• query 2 4: .
• update 4 42: được cập nhật thành 42.
• query 1 5: .

Giới hạn:

• ,