Козак Вус отримав масив $a$ з $n$ цілих чисел. Потім Козаку розповіли про існування масиву $b$ який також складається з $n$ цілих чисел, проте з яких саме Вус не знає. Для знаходження масиву $b$ Козак може будь яку кількість разів використовувати наступну операцію: \begin{itemize} \item Вибрати два цілі числа $1 \leq l \leq r \leq n$. \item Дізнатися суму $b_l + b_{l + 1} + \dots + b_r$. \item Заплатити $gcd(a_l, a_{l+1}, ..., a_r)$ копійок, де $gcd$~--- найбільший спільний дільник (наприклад $gcd(3, 5) = 1$, а $gcd(15, 30, 6) = 3$). \end{itemize} Вус просить Вас знайти мінімальну кількість копійок, необхідну для знаходження масиву $b$. Потім Козак $q$ разів змінить певне число $a_i$ на $x$. Після кожної такої зміни необхідно знайти мінімальну кількість копійок для оновленого масиву. \InputFile Перший рядок містить два цілі числа $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)$~--- індекс елемента з масиву який змінюють та число на яке змінюють. \OutputFile Виведіть $q + 1$ число~--- для кожної версії масиву $a$ знайдіть мінімальну кількість копійок необхідну для знаходження масиву $b$ Перше число~--- відповідь для початкового масиву $a$. Наступні $q$ чисел~--- відповіді для кожного оновлення масиву \Scoring \begin{enumerate} \item ($8$ балів): $n \le 10^2, q = 0$; \item ($7$ балів): $n \le 10^3, q = 0$; \item ($11$ балів): $q = 0$; \item ($12$ балів): $q \leq 100$; \item ($9$ балів): $q \leq 500$; \item ($23$ бали): $q \leq 10000$; \item ($30$ балів): без додаткових обмежень. \end{enumerate}