世界著名的题目作者 Andrew 终于决定退休了。然而，他希望在退休前发布最后一部杰作，以巩固他的声誉并惊艳全世界的选手。作为他最得意的门生，他请求你在他将题目提交给 ICFP（国际奇妙问题委员会）之前帮他校对一下。

这道题涉及相当复杂的数论知识，你最终想出了一个解法……却发现它无法通过他的数据。在浪费了数小时调试代码后，你意识到你的代码是正确的——数据本身是无效的！Andrew 的高龄似乎真的让他力不从心了。

在这道题中，你将得到一个包含 $n$ 个整数的序列 $V_{1..n}$，题目给出了一个重要保证：在每一个长度为 $k$ 的连续整数区间（即对于某个起始索引 $i$，区间为 $V_i..V_{i+k-1}$）中，任意两个整数都互质（如果两个整数除了 1 以外没有公因数，则称它们互质）。然而请注意，Andrew 提供的数据并不满足这一条件，这导致你的程序崩溃了！

为了帮助你敬爱的导师，你需要统计有多少个长度为 $k$ 的区间不满足他题目中的承诺。不幸的是，你的工作还没结束。由于难以修正他的数据，Andrew 进行了 $m$ 次顺序更新，每次更新涉及选择序列中的某个位置 $a$，并将其值修改为某个值 $b$。在每次修改后，他想知道他的新序列中包含多少个不合法的长度为 $k$ 的区间。不仅如此，在第 $m$ 次更新后，Andrew 认为数据已经足够好了，并希望你用最终得到的整数序列来解决他的问题！他的题目描述如下：

给定一个整数序列，计算它们的和。

输入格式

输入包含多组测试数据。每组测试数据的第一行包含三个整数 $n$ ($1 \le n \le 100,000$)、$k$ ($1 \le k \le n$) 和 $m$ ($1 \le m \le 100,000$)，其中 $n$ 是 Andrew 列表的大小，$k$ 是感兴趣的连续区间长度，$m$ 是 Andrew 进行的修改次数。接下来的 $n$ 行，每行包含一个整数 $v$ ($1 \le v \le 100,000$)，表示 Andrew 列表中的值。这些 $v$ 将按照它们在 Andrew 列表中出现的顺序给出。随后的 $m$ 行，每行包含一对整数 $a$ ($1 \le a \le n$) 和 $b$ ($1 \le b \le 100,000$)，表示 Andrew 将值 $V_a$ 修改为 $b$。输入以一行三个 0 结束。

输出格式

对于每组测试数据，输出 $m+2$ 个整数。第一个整数应该是 Andrew 原始列表中不满足两两互质约束的长度为 $k$ 的区间数量。接下来的 $m$ 个整数依次为 Andrew 每次修改后，序列中不满足该约束的长度为 $k$ 的区间数量。最后一个整数应该是最终列表中所有数字的和。每个整数占一行，不要包含空格。输出之间不要打印任何空行。

样例

样例输入 1

6 3 4
7
2
3
4
5
6
4 3
5 9
4 10
6 11
0 0 0

样例输出 1

2
3
3
3
2
42