[AdditionalFile5231.zip](file://AdditionalFile5231.zip?type=additional_file)

#5231. 「UOI 2021 Stage 4 Day2」科扎克·武斯与最大公约数

标签: 传统 | 时间限制: 2000 ms | 内存限制: 256 MiB |

题目描述

题目译自 Ukrainian Olympiads in Informatics 2021 Stage 4 Day2 T2. Козак Вус та НСД

科扎克·武斯获得了一个包含 $n$ 个整数的数组 $a$。随后，他得知还有一个同样包含 $n$ 个整数的数组 $b$，但他并不知道数组 $b$ 的具体内容。为了找到数组 $b$，科扎克·武斯可以任意多次使用以下操作：

• 选择两个整数 $1 \leq l \leq r \leq n$。
• 获知 $b_l + b_{l+1} + \dots + b_r$ 的和。
• 支付 $\gcd(a_l, a_{l+1}, \dots, a_r)$ 枚硬币，其中 $\gcd$ 表示最大公约数（例如 $\gcd(3, 5) = 1$，$\gcd(15, 30, 6) = 3$）。

科扎克·武斯请求你帮助他找到确定数组 $b$ 所需的最少硬币数量。

随后，科扎克·武斯会进行 $q$ 次操作，每次将数组 $a$ 中的某个数 $a_i$ 改为 $x$。在每次修改后，你需要重新计算更新后数组所需的最少硬币数量。

输入格式

第一行包含两个整数 $n$ 和 $q$ $(1 \leq n \leq 10^{5}, 0 \leq q \leq 10^{5})$，分别表示数组 $a$ 的元素数量和数组修改的次数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(1 \leq a_i \leq 10^{9})$，表示数组 $a$ 的元素。

接下来的 $q$ 行，每行包含两个整数 $i$ 和 $x$ $(1 \leq i \leq n, 1 \leq x \leq 10^{9})$，表示修改数组中第 $i$ 个元素为 $x$。

输出格式

输出 $q + 1$ 个整数，分别对应每一版本的数组 $a$ 所需的最少硬币数量，用来确定数组 $b$。

第一个数字表示初始数组 $a$ 所需的答案。

接下来的 $q$ 个数字分别表示每次更新数组后的答案。

样例 1

输入

5 3
20 40 9 25 15
3 10
5 21
4 135

输出

5
25
9
11

样例 2

输入

4 2
20 4 8 36
1 2
4 18

输出

16
8
8

数据范围与提示

详细子任务附加限制及分值如下表所示：