Kozak Vus and NSD

Cossack Vus has an array $a$ consisting of $n$ integers. He learns about another array $b$, which also has $n$ integers, but he doesn't know the values of $b$. To determine the array $b$, Vus can perform the following operation any number of times:

- Select two integers $1\le l\le r\le n$. - Discover the sum $b_l+b_{l+1}+\cdots +b_r$. - Pay $gcd(a_l,a_{l+1},...,a_r)$ coins, where $gcd$ is the greatest common divisor (e.g., $gcd(3,5)=1$, and $gcd(15,30,6)=3$).

Vus wants you to find the minimum number of coins needed to determine the array $b$.

Additionally, Vus will change a certain number $a_i$ to $x$ a total of $q$ times. After each change, you need to find the minimum number of coins required for the updated array.

Input

The first line contains two integers $n$ and $q$ $(1\le n\le 10^5,0\le q\le 10^5)$ — the number of elements in the array $a$ and the number of changes to the array.

The second line contains $n$ integers $a_1,a_2,...,a_n$ $(1\le a_i\le 10^9)$ — the elements of the array.

The next $q$ lines each contain two integers $i$ and $x$ $(1\le i\le n,1\le x\le 10^9)$ — the index of the element in the array that is changed and the new value it is changed to.

Output

Output $q+1$ numbers — for each version of the array $a$, find the minimum number of coins needed to determine the array $b$.

The first number is the answer for the initial array $a$.

The next $q$ numbers are the answers for each update of the array.

Examples

Scoring

1. ($8$ points): $n\le 10^2,q=0$;

2. ($7$ points): $n\le 10^3,q=0$;

3. ($11$ points): $q=0$;

4. ($12$ points): $q\le 100$;

5. ($9$ points): $q\le 500$;

6. ($23$ points): $q\le 10000$;

7. ($30$ points): no additional constraints.