题目描述

传说在上古时代，有一个简单的签到游戏。能通关这个游戏的幸运挑战者，将会收到一份小礼包。

签到游戏是这样的：

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

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

挑战者可以进行无限多轮操作。在一轮操作中，挑战者可以指定介于 $1$ 与 $n$ 之间的 $l,r$，花费 $\gcd_{i=l}^r Bi$ 的代价，获取第 $l$ 个至第 $r$ 个杯子里的小球总数，也即获取 $\sum{i=l}^r Ai$ 的具体数值。其中，$\gcd{i=l}^r B_i$ 表示 $\gcd(Bl,B{l+1},\dots,B_r)$。

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

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

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

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

如果你帮所有挑战者算出了正确的答案，他们会送给你一份礼物 —— 100 分。

输入格式

从标准输入读入数据。

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

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

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

输出格式

输出到标准输出。

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

样例

input

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

output

5
6
10
10
12

第一个挑战者得到的 $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\leq n\leq 10^5$，$1\leq q\leq 10^5$，$1\leq B_i\leq 10^9$，$1\leq p_i\leq n$。