Казак Ус получил массив $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}