НОД без изменений

3000 мс · 256 МБ · всё или ничего

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

Формат ввода

В первой строке $n$ и $q$ ( $1 \le n, q \le 2 \cdot 10^5$ ). Во второй — $n$ чисел $a_i$ ( $1 \le a_i \le 10^9$ ). Далее $q$ строк по два числа $l$ и $r$ .

Формат вывода

Для каждого запроса выведите НОД на отдельной строке.

Примеры

ввод

5 3
6 12 18 5 10
1 3
4 5
1 5

вывод

6
5
1

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.