환상적인 문제

문제 출제자 앤드루가 은퇴하기로 했다. 은퇴하기 전에 마지막 문제를 하나 내고 싶어서, 제자인 당신에게 ICFP(International Committee for Fantastic Problems)로 보내기 전 검수를 부탁했다.

문제는 꽤 묵직한 정수론 문제였다. 풀이를 만들어 돌려 봤지만 앤드루의 데이터를 통과하지 못했다. 몇 시간을 디버깅한 끝에, 코드는 맞고 데이터가 틀렸다는 사실을 알아냈다. 나이가 앤드루를 따라잡은 모양이다.

앤드루의 문제에서는 정수 $n$개로 이루어진 수열 $V_1, V_2, \ldots, V_n$이 주어진다. 여기에는 연속한 정수 $k$개로 이루어진 구간 $V_i, V_{i+1}, \ldots, V_{i+k-1}$ 안에서 어떤 두 정수를 골라도 서로소라는 조건이 붙어 있다. 두 정수가 서로소라는 말은 $1$ 말고는 공약수가 없다는 뜻이다. 앤드루의 데이터는 이 조건을 지키지 않고, 그래서 프로그램이 죽는다.

당신은 스승을 돕기 위해 조건을 어기는 길이 $k$짜리 구간이 몇 개인지 센다. 여기서 끝이 아니다. 앤드루는 데이터를 고치는 데 애를 먹다가 수정을 $m$번 차례로 하는데, 각 수정은 수열에서 위치 $a$를 하나 골라 그 값을 $b$로 바꾸는 것이다. 앤드루는 수정할 때마다 새 수열에 조건을 어기는 길이 $k$짜리 구간이 몇 개 남았는지 알고 싶어 한다. $m$번째 수정까지 끝나면 앤드루는 데이터가 쓸 만해졌다고 판단하고, 그렇게 만들어진 수열로 원래 문제를 풀어 달라고 한다. 문제는 이렇다. 정수 수열이 주어질 때 그 합을 구하여라.

입력에는 테스트 케이스가 여러 개 들어 있다. 각 테스트 케이스의 첫 줄에는 정수 $n$ ($1 \le n \le 100000$), $k$ ($1 \le k \le n$), $m$ ($1 \le m \le 100000$)이 주어진다. $n$은 앤드루가 만든 목록의 길이, $k$는 살펴볼 구간의 길이, $m$은 앤드루가 하는 수정 횟수다. 다음 $n$개 줄에는 목록에 들어 있는 값 $v$ ($1 \le v \le 100000$)가 한 줄에 하나씩, 목록에 놓인 순서대로 주어진다. 이어지는 $m$개 줄에는 정수 $a$ ($1 \le a \le n$)와 $b$ ($1 \le b \le 100000$)가 한 쌍씩 주어지며, 앤드루가 $V_a$를 $b$로 바꿨다는 뜻이다. 입력의 마지막 줄에는 0이 세 개 주어진다.

각 테스트 케이스마다 정수 $m + 2$개를 한 줄에 하나씩, 공백 없이 출력한다. 첫 번째 정수는 앤드루의 원래 목록에서 두 수가 서로소여야 한다는 조건을 어기는 길이 $k$짜리 구간의 개수다. 이어지는 $m$개 정수는 각 수정 직후에 조건을 어기는 길이 $k$짜리 구간의 개수를 순서대로 나타낸다. 마지막 정수는 최종 목록에 있는 수의 합이다. 출력 사이에 빈 줄을 넣지 않는다.