Казак Ус и НОД

Казак Ус получил массив $a$ из $n$ целых чисел. Затем Казаку рассказали о существовании массива $b$ который также состоит из $n$ целых чисел, однако из каких именно Ус не знает. Для нахождения массива $b$ Казак может любое количество раз использовать следующую операцию:

• Выбрать два целых числа $1\le l\le r\le n$.

• Узнать сумму $b_l+b_{l+1}+\cdots +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$. После каждого такого изменения необходимо найти минимальное количество копеек для обновленного массива.

Входные данные

Первая строка содержит два целых числа $n$ и $q$ $(1\le n\le 10^5,0\le q\le 10^5)$ — количество элементов массива $a$ и количество изменений массива.

Вторая строка содержит $n$ целых чисел $a_1,a_2,...,a_n$ $(1\le a_i\le 10^9)$ — элементы массива.

Следующие $q$ строк содержат по два целых числа $i$ и $x$ $(1\le i\le n,1\le x\le 10^9)$ — индекс элемента массива который меняют и число на которое меняют.

Выходные данные

Выведите $q+1$ число — для каждой версии массива $a$ найдите минимальное количество копеек необходимое для нахождения массива $b$

Первое число — ответ исходного массива $a$.

Следующие $q$ чисел — ответы для каждого обновления массива

Примеры

Оценивание

1. ($8$ баллов): $n\le 10^2,q=0$;

2. ($7$ баллов): $n\le 10^3,q=0$;

3. ($11$ баллов): $q=0$;

4. ($12$ баллов): $q\le 100$;

5. ($9$ баллов): $q\le 500$;

6. ($23$ балла): $q\le 10000$;

7. ($30$ баллов): без дополнительных ограничений.