D. НОД массива
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$ длины $$$n$$$. Требуется обработать $$$q$$$ запросов следующего вида: даны два целых числа $$$i$$$ и $$$x$$$, необходимо умножить элемент $$$a_i$$$ на $$$x$$$.

После обработки каждого запроса нужно вывести наибольший общий делитель (НОД) всех чисел массива $$$a$$$.

Так как ответ может быть слишком большим, вам требуется вывести его по модулю $$$10^9+7$$$.

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

Первая строка входных данных содержит два целых числа — $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$).

Вторая строка содержит $$$n$$$ натуральных чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — элементы массива $$$a$$$ до изменений.

Следующие $$$q$$$ строк содержат запросы в следующем формате: в каждой строке содержатся два целых числа $$$i$$$ и $$$x$$$ ($$$1 \le i \le n$$$, $$$1 \le x \le 2 \cdot 10^5$$$).

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

Выведите $$$q$$$ строк: после выполнения каждого запроса выведите НОД всех чисел массива по модулю $$$10^9+7$$$ в отдельной строке.

Пример
Входные данные
4 3
1 6 8 12
1 12
2 3
3 3
Выходные данные
2
2
6
Примечание

После первого запроса массив станет $$$[12, 6, 8, 12]$$$, $$$\operatorname{gcd}(12, 6, 8, 12) = 2$$$.

После второго запроса — $$$[12, 18, 8, 12]$$$, $$$\operatorname{gcd}(12, 18, 8, 12) = 2$$$.

После третьего запроса — $$$[12, 18, 24, 12]$$$, $$$\operatorname{gcd}(12, 18, 24, 12) = 6$$$.

Здесь функция $$$\operatorname{gcd}$$$ обозначает наибольший общий делитель.