Казак Ус получил массив a из n целых чисел. Затем Казаку рассказали о существовании массива b который также состоит из n целых чисел, однако из каких именно Ус не знает. Для нахождения массива b Казак может любое количество раз использовать следующую операцию:
Выбрать два целых числа 1≤l≤r≤n.
Узнать сумму bl+bl+1+⋯+br.
Заплатить gcd(al,al+1,...,ar) копеек, где gcd — наибольший общий делитель (например gcd(3,5)=1, а gcd(15,30,6)=3).
Ус просит Вас найти минимальное количество копеек, необходимое для нахождения массива b.
Затем Казак q раз изменит определенное число ai на x. После каждого такого изменения необходимо найти минимальное количество копеек для обновленного массива.
Первая строка содержит два целых числа n и q (1≤n≤105,0≤q≤105) — количество элементов массива a и количество изменений массива.
Вторая строка содержит n целых чисел a1,a2,...,an (1≤ai≤109) — элементы массива.
Следующие q строк содержат по два целых числа i и x (1≤i≤n,1≤x≤109) — индекс элемента массива который меняют и число на которое меняют.
Выведите q+1 число — для каждой версии массива a найдите минимальное количество копеек необходимое для нахождения массива b
Первое число — ответ исходного массива a.
Следующие q чисел — ответы для каждого обновления массива
(8 баллов): n≤102,q=0;
(7 баллов): n≤103,q=0;
(11 баллов): q=0;
(12 баллов): q≤100;
(9 баллов): q≤500;
(23 балла): q≤10000;
(30 баллов): без дополнительных ограничений.