Cerința

Se dă un vector indexat de la 1 cu n elemente numere naturale. Să se răspundă la q întrebări de forma x y, cu semnificația: “Care este cel mai mare divizor comun al elementelor cu indici cuprinși între x și y, inclusiv?”

Date de intrare

Fișierul de intrare divquery.in conține pe prima linie numerele n și q, pe a doua linie cele n numere naturale ale vectorului, iar de la linia 3 începând, q linii, pe fiecare aflându-se doua numere x y, reprezentând întrebările.

Date de ieșire

Fișierul de ieșire divquery.out va conține q linii, pe fiecare linie i aflându-se răspunsul la întrebarea i.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• 1 ≤ ai ≤ 100.000
• 1 ≤ q ≤ 1.000.000

Exemplu:

divquery.in

5 4
1 3 18 2 3
1 5
2 3
3 4
2 4

divquery.out

1
3
2
1

Explicație

În intervalul [1,5] cmmdc-ul este 1
În intervalul [2,3] cmmdc-ul este 3
În intervalul [3,4] cmmdc-ul este 2
În intervalul [2,4] cmmdc-ul este 1