C. НОД на отрезке
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Вам дан массив a1, a2, ..., an, состоящий из целых положительных чисел. Так же вам даны m запросов вида li, ri. В ответ на i-ый запрос нужно вывести наибольший общий делитель чисел ali, ali + 1, ..., ari.

Входные данные

В первой строке записаны два целых числа n, m (1 ≤ n, m ≤ 50000). Во второй строке записан массив a1, a2, ..., an (1 ≤ ai ≤ 109). В следующих m строках записаны пары целых чисел li, ri (1 ≤ li ≤ ri ≤ n) — запросы.

Выходные данные

В ответ на каждый запрос выведите наибольший общий делитель элементов массива из соответствующего отрезка.

Примеры
Входные данные
10 13
18 12 18 12 12 15 18 9 18 6
4 9
10 10
8 10
6 6
2 6
4 5
7 9
1 7
1 5
1 1
3 4
6 7
6 9
Выходные данные
3
6
3
15
3
12
9
3
6
18
6
3
3