An có một dãy số nguyên dương. Với mỗi truy vấn \((l, r)\), An muốn tìm ước số chung lớn nhất (GCD) lớn nhất có thể của hai phần tử kề nhau trong đoạn. Nói cách khác, hãy tìm giá trị lớn nhất của \(\gcd(A_i, A_{i+1})\) với \(l \le i < 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^5\)).
• \(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 lớn nhất tìm được. Nếu \(l = r\), in ra \(0\).

Ví dụ

Input:

6 3
12 18 24 7 14 21
1 4
3 6
1 3

Output:

6
7
6