Казак Ус и НОД
Казак Ус и НОД
Казак Ус получил массив a из n целых чисел. Затем Казаку рассказали о существовании массива b который также состоит из n целых чисел, однако из каких именно Ус не знает. Для нахождения массива b Казак может любое количество раз использовать следующую операцию:
Выбрать два целых числа 1 \leq l \leq r \leq n.
Узнать сумму b_l + b_{l + 1} + \dots + b_r.
Заплатить gcd(a_l, a_{l+1}, ..., a_r) копеек, где gcd — наибольший общий делитель (например gcd(3, 5) = 1, а gcd(15, 30, 6) = 3).
Ус просит Вас найти минимальное количество копеек, необходимое для нахождения массива b.
Затем Казак q раз изменит определенное число a_i на x. После каждого такого изменения необходимо найти минимальное количество копеек для обновленного массива.
Input data
Первая строка содержит два целых числа n и q(1 \leq n \leq 10^5, 0 \leq q \leq 10^5) — количество элементов массива a и количество изменений массива.
Вторая строка содержит n целых чисел a_1, a_2, ..., a_n(1 \leq a_i \leq 10^9) — элементы массива.
Следующие q строк содержат по два целых числа i и x(1 \leq i \leq n, 1 \leq x \leq 10^9) — индекс элемента массива который меняют и число на которое меняют.
Output data
Выведите q + 1 число — для каждой версии массива a найдите минимальное количество копеек необходимое для нахождения массива b
Первое число — ответ исходного массива a.
Следующие q чисел — ответы для каждого обновления массива
Examples
5 3 20 40 9 25 15 3 10 5 21 4 135
5 25 9 11
4 2 20 4 8 36 1 2 4 18
16 8 8
Scoring
(8 баллов): n \le 10^2, q = 0;
(7 баллов): n \le 10^3, q = 0;
(11 баллов): q = 0;
(12 баллов): q \leq 100;
(9 баллов): q \leq 500;
(23 балла): q \leq 10000;
(30 баллов): без дополнительных ограничений.