Дан массив $$$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}$$$ обозначает наибольший общий делитель.
| Codeforces Round 705 (Div. 2) |
|---|
| Закончено |
