Description

你有一个长度为 $N$ 的序列 $A = (A_1, A_2, \dots, A_N)$，初始时所有元素均为 $0$。

你还得到一个整数 $K$，定义函数 $f(A)$ 如下：

设 $B$ 为将序列 $A$ 按非递增（降序）排序后的结果；

那么 $f(A) = B_1 + B_2 + \cdots + B_K$，即 $A$ 中最大的 $K$ 个数之和。

你将对序列 $A$ 进行 $Q$ 次更新。对于第 $i$ 次更新：

将 $A_{X_i}$ 设置为 $Y_i$。

每次操作后，输出当前序列 $A$ 的 $f(A)$ 值。

Format

Input

第一行包含三个整数 $N, K, Q$（$1 \le K \le N \le 5 \times 10^5$, $1 \le Q \le 5 \times 10^5$）——序列长度、参数 $K$ 和操作次数。

接下来 $Q$ 行，每行两个整数 $X_i, Y_i$（$1 \le X_i \le N$, $0 \le Y_i \le 10^9$），表示将 $A_{X_i}$ 设为 $Y_i$。

Output

输出共 $Q$ 行，每行一个整数，第 $i$ 行输出第 $i$ 次操作后 $f(A)$ 的值。

Samples

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

5
6
8
8
15
13
13
11
1
0