题目描述

出题人有 $n$ 个不透明的杯子，倒扣在桌面上，排成一列。这些杯子从左到右依次编号为 $1$ 至 $n$，第 $i$ 个杯子里放着 $A_i$ 个小球。当然，由于杯子是不透明且倒扣着的，挑战者并不知道 $A_i$ 的具体数值。

出题人对于第 $i$ 个杯子还设置了一个权值 $B_i$，$B_i$ 对挑战者公开。

挑战者可以进行无限多轮操作。在一轮操作中，挑战者可以指定介于 $1$ 与 $n$ 之间的 $l,r$，花费

$$\gcd_{i=l}^{r} B_i$$

的代价，获取第 $l$ 个至第 $r$ 个杯子里的小球总数，也即获取

$$\sum_{i=l}^{r} A_i$$

的具体数值。其中，

$$\gcd_{i=l}^{r} B_i = \gcd(B_l,B_{l+1},\ldots,B_r)$$

挑战者需要达成的目标是：用尽量小的代价，正确地回答出题人每个杯子里放着多少个小球，也即回答对于 $1\le i\le n$，$A_i$ 的具体数值。

现在，有 $q$ 个挑战者依次进行挑战。他们将告知你他们得到的 $B_i$，并希望你帮忙求出每个人为保证达成目标所需的最小代价。

经过你的观察，在第 $k$ 个挑战者挑战前，出题人会在上个挑战者的 $\{A_i\},\{B_i\}$ 基础上，不改变 $n$，重新随机生成 $\{A_i\}$，并修改 $B$ 序列的某个特定位置 $p_k$ 为 $B_{p_k}$，其余不变。

对于第一个挑战者，出题人会在初始序列的基础上修改。

输入格式

第一行为两个整数 $n,q$，分别表示出题人的杯子个数与挑战者个数。

第二行为 $n$ 个正整数，第 $i$ 个正整数表示初始时的 $B_i$。

接下来 $q$ 行中，第 $k$ 行两个正整数 $p_k,B_{p_k}$，表示第 $k$ 个人挑战前出题人修改 $B$ 序列的位置与修改后的数值。

输出格式

输出 $q$ 行，第 $k$ 行为一个整数，表示第 $k$ 个挑战者达成目标所需要的最小代价。

样例 1

样例输入 1

5 5
1 2 3 4 5
1 2
3 4
5 6
1 8
2 4

样例输出 1

5
6
10
10
12

样例解释 1

第一个挑战者得到的 $B=\{2,2,3,4,5\}$，可以证明，其最优选择之一为：

$$[1,5],\ [1,3],\ [2,5],\ [1,4],\ [3,5]$$

最小代价为 $5$。其中 $[x,y]$ 表示一次 $l=x,r=y$ 的操作。

第二个挑战者得到的 $B=\{2,2,4,4,5\}$，可以证明，其最优选择之一为：

$$[1,4],\ [3,5],\ [1,5],\ [4,5],\ [2,5]$$

最小代价为 $6$。

对于其他的挑战者不再赘述。

其余样例见下发文件。

数据范围

对于所有数据，保证：

$$1\le n\le 10^5, \qquad 1\le q\le 10^5, \qquad 1\le B_i\le 10^9, \qquad 1\le p_i\le n$$

子任务编号	分值	$n\le$	$q\le$	特殊性质
1	10	$200$		无
2	20	$10^5$	$1$
3	25		$1000$
4	10		$10^5$	$B_i$ 在 $[1,10^9]$ 的整数中等概率随机分布
5	35			无