Козак Вус та НСД#10447
Козак Вус отримав масив з цілих чисел. Потім Козаку розповіли про існування масиву який також складається з цілих чисел, проте з яких саме Вус не знає. Для знаходження масиву Козак може будь-яку кількість разів використовувати наступну операцію:
Вибрати два цілі числа 1 \leq l \leq r \leq n.
Дізнатися суму b_l + b_{l + 1} + \dots + b_r.
Заплатити gcd(a_l, a_{l+1}, ..., a_r) копійок, де — найбільший спільний дільник (наприклад gcd(3, 5) = 1, а gcd(15, 30, 6) = 3).
Вус просить Вас знайти мінімальну кількість копійок, необхідну для знаходження масиву .
Потім Козак разів змінить певне число a_i на . Після кожної такої зміни необхідно знайти мінімальну кількість копійок для оновленого масиву.
Перший рядок містить два цілі числа та (1 \leq n \leq 10^5, 0 \leq q \leq 10^5) — кількість елементів масиву та кількість змін масиву.
Другий рядок містить цілих чисел a_1, a_2, ..., a_n (1 \leq a_i \leq 10^9) — елементи масиву.
Наступні рядків містять по два цілі числа та (1 \leq i \leq n, 1 \leq x \leq 10^9) — індекс елемента з масиву який змінюють та число на яке змінюють.
Виведіть q + 1 число — для кожної версії масиву знайдіть мінімальну кількість копійок необхідну для знаходження масиву
Перше число — відповідь для початкового масиву .
Наступні чисел — відповіді для кожного оновлення масиву
Приклад 1
Приклад 2
( балів): n \le 10^2, q = 0;
( балів): n \le 10^3, q = 0;
( балів): q = 0;
( балів): q \leq 100;
( балів): q \leq 500;
( бали): q \leq 10000;
( балів): без додаткових обмежень.