题目描述

我们有一个长度为$N$的序列$A=(A_1,A_2, \dots, A_N)$。初始时，所有项均为$0$。 使用输入中给定的整数$K$，我们定义一个函数$f(A)$如下：

• 令$B$是通过以降序对$A$进行排序得到的序列（使其单调非递增）。
• 然后，令$f(A)=B_1 + B_2 + \dots + B_K$。

我们考虑在这个序列上应用$Q$次更新。 按照以下顺序对序列$A$应用操作，其中$i=1,2,\dots,Q$，并在每次更新结束后打印出$f(A)$的值。

• 将$A_{X_i}$更改为$Y_i$。

约束条件

• 所有输入值均为整数。
• $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$

输入

输入以以下格式从标准输入中给出：

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

输出

共输出$Q$行。第$i$行应该包含当第$i$次更新结束时的整数值$f(A)$。

示例输入1

4 2 10
1 5
2 1
3 3
4 2
2 10
1 0
4 0
3 1
2 0
3 0

示例输出1

5
6
8
8
15
13
13
11
1
0

在这个输入中，$N=4$，$K=2$。应用了$Q=10$次更新。

• 第$1$次更新使得$A=(5, 0,0,0)$。此时，$f(A)=5$。
• 第$2$次更新使得$A=(5, 1,0,0)$。此时，$f(A)=6$。
• 第$3$次更新使得$A=(5, 1,3,0)$。此时，$f(A)=8$。
• 第$4$次更新使得$A=(5, 1,3,2)$。此时，$f(A)=8$。
• 第$5$次更新使得$A=(5,10,3,2)$。此时，$f(A)=15$。
• 第$6$次更新使得$A=(0,10,3,2)$。此时，$f(A)=13$。
• 第$7$次更新使得$A=(0,10,3,0)$。此时，$f(A)=13$。
• 第$8$次更新使得$A=(0,10,1,0)$。此时，$f(A)=11$。
• 第$9$次更新使得$A=(0, 0,1,0)$。此时，$f(A)=1$。
• 第$10$次更新使得$A=(0, 0,0,0)$。此时，$f(A)=0$。