We have a sequence $A=(A_1,A_2,\dots,A_N)$ of length $N$. Initially, all the terms are $0$.  
Using an integer $K$ given in the input, we define a function $f(A)$ as follows:

-   Let $B$ be the sequence obtained by sorting $A$ in descending order (so that it becomes monotonically non-increasing).
-   Then, let $f(A)=B_1 + B_2 + \dots + B_K$.

We consider applying $Q$ updates on this sequence.  
Apply the following operation on the sequence $A$ for $i=1,2,\dots,Q$ in this order, and print the value $f(A)$ at that point after each update.

-   Change $A_{X_i}$ to $Y_i$.

The input is given from Standard Input in the following format:

```
$N$ $K$ $Q$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_Q$ $Y_Q$
```

Print $Q$ lines in total. The $i$-th line should contain the value $f(A)$ as an integer when the $i$-th update has ended.

-   All input values are integers.
-   $1 \le K \le N \le 5 \times 10^5$
-   $1 \le Q \le 5 \times 10^5$
-   $1 \le X_i \le N$
-   $0 \le Y_i \le 10^9$

5
6
8
8
15
13
13
11
1
0

In this input, N=4 and K=2. Q=10 updates are applied.

• The 1-st update makes A=(5,0,0,0). Now, f(A)=5.
• The 2-nd update makes A=(5,1,0,0). Now, f(A)=6.
• The 3-rd update makes A=(5,1,3,0). Now, f(A)=8.
• The 4-th update makes A=(5,1,3,2). Now, f(A)=8.
• The 5-th update makes A=(5,10,3,2). Now, f(A)=15.
• The 6-th update makes A=(0,10,3,2). Now, f(A)=13.
• The 7-th update makes A=(0,10,3,0). Now, f(A)=13.
• The 8-th update makes A=(0,10,1,0). Now, f(A)=11.
• The 9-th update makes A=(0,0,1,0). Now, f(A)=1.
• The 10-th update makes A=(0,0,0,0). Now, f(A)=0.