Cho một dãy số nguyên dương gồm N phần tử ~a_1, a_2, a_3, …, a_N~ và một số nguyên dương Q tương ứng với số lượng truy vấn.

Mỗi truy vấn có dạng L, R (~L≤ R ≤ N~). Với mỗi đoạn con (u, v) thuộc đoạn L, R (~L ≤ u ≤ v ≤ R~) tìm đoạn con có UCNN lớn nhất.

Yêu cầu:

Viết chương trình giải quyết Q truy vấn.

Dữ liệu: Từ tệp văn bản SUBGCD.INP.

• Dòng đầu tiên là 2 số nguyên dương N, Q. (~N, Q≤10^5~)

• Dòng tiếp theo gồm N số nguyên dương ~a_1, a_2, a_3, …, a_N~.(~a_i ≤ 10^6~)

• Q dòng tiếp theo mỗi dòng là 2 số nguyên L, R.

Kết quả: Ghi ra tệp văn bản SUBGCD.OUT Q dòng, mỗi dòng là UCNN lớn nhất tìm được.

Ví dụ: SUBGCD.INP

5 2
1 2 2 6 8
1 3
2 4

SUBGCD.OUT

2
6

Ràng buộc

Subtask 1: (30% số điểm) có N, Q≤500

Subtask 2: (40% số điểm) có N, Q≤5000

Subtask 3: (40% số điểm) có N, Q≤105 và ~|L_i – L_i-1|~ = 1 và |~R_i – R_i-1~| = 1