Fantastic Problem

Andrew is a problem setter, and he has decided to retire. He wants to put out one last problem before he stops, so he asked you, his student, to proofread it before he sends it to the ICFP (International Committee for Fantastic Problems).

The problem turns out to be a heavy piece of number theory. You put a solution together, and it fails on his data. After hours of debugging you find that your code is right and the data is wrong. Andrew's age has caught up with him.

In his problem you are given a sequence of $n$ integers $V_1, V_2, \ldots, V_n$, with the promise that inside every interval of $k$ consecutive integers $V_i, V_{i+1}, \ldots, V_{i+k-1}$, any two integers are coprime. Two integers are coprime when $1$ is their only common factor. Andrew's data breaks the promise, and that is what makes your program crash.

To help your mentor, you count how many intervals of size $k$ fail the promise. That is not the end of it. Andrew has trouble fixing the data, so he makes $m$ changes one after another, and each change picks a position $a$ in the sequence and sets its value to $b$. After every change he wants to know how many invalid intervals of size $k$ the new sequence contains. Once the $m$-th change is done, Andrew decides the data is good enough and asks you to solve his problem on the resulting sequence. His problem statement is this: given a sequence of integers, compute their sum.

The input holds several test cases. Each test case begins with a line of three integers $n$ ($1 \le n \le 100000$), $k$ ($1 \le k \le n$) and $m$ ($1 \le m \le 100000$), where $n$ is the length of Andrew's list, $k$ is the size of the intervals of interest, and $m$ is the number of changes Andrew makes. Each of the next $n$ lines holds one integer $v$ ($1 \le v \le 100000$), a value in Andrew's list. The values appear in the order they appear in the list. Each of the following $m$ lines holds a pair of integers $a$ ($1 \le a \le n$) and $b$ ($1 \le b \le 100000$), meaning that Andrew has changed $V_a$ to $b$. The input ends with a line holding three zeros.

For each test case, print $m + 2$ integers, each on its own line and with no spaces. The first integer is the number of size-$k$ intervals in Andrew's original list that fail the pairwise-coprime constraint. Each of the next $m$ integers is the number of size-$k$ intervals that fail the constraint after the matching change, in order. The last integer is the sum of the numbers in the final list. Print no blank lines between outputs.