Tèo có một dãy số nguyên dương. Cậu muốn kiểm tra tính chia hết của các số trong một đoạn bất kỳ. Cụ thể, với mỗi truy vấn \((l, r)\), Tèo muốn biết ước số chung lớn nhất (GCD) của tất cả các phần tử từ \(l\) đến \(r\).

Ràng buộc

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

• Dòng đầu chứa hai số nguyên \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l, r\) (\(1 \le l \le r \le N\)).

Định dạng đầu ra

• Ứng với mỗi truy vấn, in ra GCD của các phần tử trong đoạn.

Ví dụ

Input:

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

Output:

6
4
2