Boring Lectures

You have a schedule of $N$ upcoming lectures, and you may choose to attend some of them. The lectures are numbered from $1$ to $N$ in chronological order. In the current schedule, the $i$-th lecture has quality $a_i$. Most of the lectures are boring, so you will attend only one group of $K$ consecutive lectures and skip the rest, so that you can sleep and prepare for programming contests. You do not like taking notes, so you can remember the content of only $2$ of the lectures you attend. Choose the group of $K$ consecutive lectures and the $2$ lectures you remember so that the sum of the qualities of those $2$ lectures is as large as possible.

There are $Q$ changes to the schedule. The $j$-th change is given by two values $i_j$ and $x_j$, which mean that the quality of the $i_j$-th lecture becomes $x_j$. For each of the $Q+1$ versions of the schedule, find the maximum possible sum of lecture qualities.

The first line contains three integers $N$, $K$, and $Q$ ($2 \le N \le 10^6$, $2 \le K \le N$, $0 \le Q \le 10^5$). The second line contains $N$ integers $a_1, \ldots, a_N$ ($0 \le a_i \le 10^9$). Each of the next $Q$ lines contains two integers $i_j$ and $x_j$ ($1 \le i_j \le N$, $0 \le x_j \le 10^9$).

Print $Q+1$ lines. The $j$-th line is the answer for the schedule after the first $j-1$ changes have been applied.