THỰC HÀNH

Cho dãy số nguyên dương a₁, a₂, …, a_n và q truy vấn, mỗi truy vấn  là một cặp số u, v (1 ≤ u ≤ v ≤ n). Bạn cần trả lới UCLN của các số a_u, a_{u + 1}, …, a_v.

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương n và q là số phần tử của dãy và số truy vấn.
• Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, a_n.
• q dòng sau, mỗi dòng chứa hai số nguyên u, v.

Hai số liên tiếp trên một dòng cách nhau một khoảng trắng.

Dữ liệu ra:

In ra trên một dòng q số nguyên ứng với q truy vấn. Hai số liên tiếp cách nhau một khoảng trắng.

Ví dụ:

Dữ liệu vào:
4 3
3 6 4 8
1 2
1 3
2 4

Dữ liệu ra:
3 1 2

Giới hạn: 1 ≤ n ≤ 10⁵; 1 ≤ q ≤ 10⁶; 1≤ a ≤ 10¹²