Note: This problem is an online version of the original version held at CCO. Differences in the problem statement will be bolded. Note that the specifics of this problem are not set in stone, so constraints/limits/test data may change without notice. Feel free to submit strong test data for this problem if non-intended solutions AC.

Canadian Computing Olympiad: 2018 Day 2, Problem 2

You have a schedule of $N$ upcoming lectures that you have the option of attending. The lectures are numbered from $1$ to $N$ and are in chronological order. From the current schedule, you expect that the $i^{th}$ lecture will have quality $a_i$. Since most of the lectures will be boring, you are only willing to attend some group of $K$ consecutive lectures. You will skip the remaining lectures so that you can catch up on sleep and participate in programming contests. Since you don't like taking notes, you will only be able to remember the content from $2$ of the lectures you attend. You want to choose the lectures you attend and the $2$ lectures you remember as to maximize the sum of the lecture qualities of those $2$ lectures.

There are $Q$ changes that will be made to the schedule. The $j^{th}$ change to the schedule is represented by two values $i_j,x_j$ that indicate that the quality of the $i_j^{th}$ lecture changes to $x_j$. For each of the $Q+1$ versions of the schedule, find the maximum possible sum of lecture qualities that you can attain.

Input Specification

The first line will contain three integers $N$, $K$, and $Q$ $(2\le N\le {10}^6,2\le K\le N,0\le Q\le {\mathbf{10}}^{\mathbf{6}})$. The second line will contain $N$ integers $a_1,\dots ,a_N$ $(0\le a_i\le {10}^9)$. The next $Q$ lines each contain two encoded integers $i_j$ and $x_j$ $(1\le i_j\le N,0\le x_j\le {10}^9)$. To decode line $2+K$ of the input, XOR all of the integers in that line with the integer printed in line $K$ of the output.

For 10 of the 25 available marks, $N\le {10}^5$ and $Q\le {10}^5$.

Output Specification

Output $Q+1$ lines, each containing a single integer. The $j^{th}$ line that follows should contain the answer for the schedule obtained after the first $j-1$ changes are made.

Sample Input

4 3 1
6 1 2 4
9 11

Output for Sample Input

8
6

Explanation for Output for Sample Input

For the original schedule, it is best to attend the first three lectures and remember the first and third, for an overall value of $6+2=8$. After the update, it is best to attend the last three lectures and remember the last two, giving a value of $2+4=6$.

Note that we XOR the integers in line 3 with 8, to get the true values, 1 3.