Козак Вус та НСД

Козак Вус отримав масив $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$. Після кожної такої зміни необхідно знайти мінімальну кількість копійок для оновленого масиву.

Input

Перший рядок містить два цілі числа $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)$ — індекс елемента з масиву який змінюють та число на яке змінюють.

Output

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

Перше число — відповідь для початкового масиву $a$.

Наступні $q$ чисел — відповіді для кожного оновлення масиву

Examples

Scoring

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$ балів): без додаткових обмежень.