Дан массив \(a\) длины \(n\). Требуется обработать \(q\) запросов следующего вида: даны два целых числа \(i\) и \(x\), необходимо умножить элемент \(a_i\) на \(x\).
После обработки каждого запроса нужно вывести наибольший общий делитель (НОД) всех чисел массива \(a\).
Так как ответ может быть слишком большим, вам требуется вывести его по модулю \(10^9+7\).
Примечание
После первого запроса массив станет \([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}\) обозначает наибольший общий делитель.