Andrew, the world-renowned problem writer, has finally
decided to retire. However, he first wishes to put out one
final masterpiece to seal his legacy and amaze competitors the
world over. As you’re his favorite pupil, he’s asked you to
help him proofread it before he submits it to the ICFP
(International Committee for Fantastic Problems).
The problem proves to be quite the involved number theory
affair, but you get together a solution eventually…only to find
that it doesn’t pass his data. After wasting hours debugging
your code, you realize that it’s correct – the data is invalid!
Andrew’s advanced age seems to have really caught up with
him.
In his problem, you’re given a sequence of integers, , with the important
guarantee that within every interval of consecutive integers (, for some
starting index ), any
two integers will be coprime (two integers are coprime if they
share no common factors besides 1). Note, however, this
condition is not met in Andrew’s data, causing your program to
crash!
In an attempt to help your beloved mentor out, you count how
many size- intervals
don’t satisfy his problem statement’s promise. Unfortunately,
your work is not done yet. Having difficulty fixing his data,
Andrew makes
sequential updates, where each update involves selecting some
position in the number
sequence, and changing its value to some value . After each change, he wants to
know how many invalid size- intervals his new sequence
contains. As if that wasn’t enough, after the update, Andrew decides that
the data is good enough, and wants you to solve his problem
with the resulting sequence of integers! His problem statement
is as follows:
Given a sequence of integers, compute their sum.
Input
There will be a single test case in the input. This test
case will begin with a line with three integers, (), () and (), where is the size of Andrew’s list,
is the size of the
consecutive intervals of interest, and is the number of changes Andrew
makes. On each of the next lines will be a single integer
(), which is a
value in Andrew’s input. The ’s will be in the order that they
appear in Andrew’s list. On each the following lines will be a pair of integers
() and (), indicating that Andrew has
changed value to be
.
Output
For each test case, output integers. The first integer
should be the number of size- intervals in Andrew’s original
list which fail the pairwise-coprime constraint. Each of the
next integers should
be the number of size-
intervals that fail the constraint after each of Andrew’s m
changes, in order. The final integer should be the sum of the
numbers in the final list. Output each integer on its own line,
with no spaces.
Sample Input 1 |
Sample Output 1 |
6 3 4
7
2
3
4
5
6
4 3
5 9
4 10
6 11
|
2
3
3
3
2
42
|