时间限制：1秒　　内存限制：256M

---

【题目描述】

　　出题人有𝑛个不透明的杯子，倒扣在桌面上，排成一列。这些杯子从左到右依次编号为 1 至 𝑛，第 𝑖 个杯子里放着 𝐴𝑖 个小球。当然，由于杯子是不透明且倒扣着的，挑战者并不知道 𝐴𝑖 的具体数值。
　　出题人对于第 𝑖 个杯子还设置了一个权值 𝐵𝑖，𝐵𝑖 对挑战者公开。
　　挑战者可以进行无限多轮操作。在一轮操作中，挑战者可以指定介于 1 与 𝑛 之间的 𝑙,𝑟，花费 \(gcd(B_l,B_{l+1},...,B_r)\) 的代价，获取第 𝑙 个至第 𝑟 个杯子里的小球总数，也即获取 $A_l+A_l+1+...+A_r 的具体数值。
　　挑战者需要达成的目标是：用尽量小的代价，正确地回答出题人，每个杯子里放着多少个小球，也即回答对于 1≤𝑖≤𝑛，𝐴𝑖 的具体数值。
　　现在，有 𝑞 个挑战者依次进行挑战。他们将告知你他们得到的 𝐵𝑖，并希望你帮忙求出每个人为保证达成目标所需的最小代价。
　　经过你的观察，在第 𝑘 个挑战者挑战前，出题人会在上个挑战者的 {𝐴𝑖},{𝐵𝑖} 基础上，不改变 𝑛，重新随机生成 {𝐴𝑖}，并修改 𝐵 序列的某个特定位置 𝑝𝑘 为 𝐵𝑝𝑘，其余不变。
　　对于第一个挑战者，出题人会在初始序列的基础上修改。

【输入格式】

　　第一行为三个整数 𝑐,𝑛,𝑞，分别表示测试点编号（特别的：样例的 𝑐=0）、出题人的杯子个数、挑战者个数。
　　第二行为 𝑛 个正整数，第 𝑖 个正整数表示初始时的 𝐵𝑖。
　　接下来 𝑞 行中，第 𝑘 行两个正整数 𝑝𝑘,𝐵𝑝𝑘，表示第 𝑘 个人挑战前出题人修改 B 序列的位置，与修改后的数值。

【输出格式】

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

【输入输出样例】

　Input

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

　Output

5
6
10
10
12

【样例说明】

　　第一个挑战者得到的 𝐵={2,2,3,4,5}，可以证明，其最优选择之一为[1,5],[1,3],[2,5],[1,4],[3,5]，最小代价为 5。其中 [𝑥,𝑦] 表示一次 𝑙=𝑥,𝑟=𝑦 的操作。
　　第二个挑战者得到的 𝐵={2,2,4,4,5}，可以证明，其最优选择之一为[1,4],[3,5],[1,5],[4,5],[2,5]，最小代价为 6。
对于其他的挑战者不再赘述。

【数据限制】

　　对于所有数据，保证有 1≤𝑛≤105，1≤𝑞≤105，1≤𝐵𝑖≤109，1≤𝑝𝑖 ≤𝑛。
　　所有测试数据的范围和特点如下表所示：

　　其中，“特殊性质”一列中的数字意义如下：
　　特殊性质 1：𝐵𝑖 在 [1,109] 的整数中等概率随机分布。

【来源】

　　Mr.he