Trong một giải đấu thể thao điện tử, có ~N~ người chơi. Ban đầu điểm số của tất cả người chơi đều bằng ~0~. Sau mỗi trận đấu, bảng điểm có thể được cập nhật. Cụ thể sẽ có ~Q~ lần cập nhật, mỗi lần cập nhật có dạng: người chơi ~X_i~ được cập nhật điểm số thành ~Y_i~.

Sau mỗi lần cập nhật, ban tổ chức muốn biết tổng điểm của ~K~ người chơi có điểm số cao nhất hiện tại. Gọi ~A = (A_1, A_2, \dots, A_N)~ là dãy điểm hiện tại. Ta định nghĩa hàm ~f(A)~ như sau:

• Sắp xếp dãy ~A~ theo thứ tự không tăng để được dãy ~B~.

• Khi đó ~f(A) = B_1 + B_2 + \dots + B_K~.

Sau mỗi lần cập nhật, hãy in ra giá trị của ~f(A)~.

Input

• Dòng đầu tiên chứa ba số nguyên ~N, K, Q~.

• ~Q~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~X_i, Y_i~ - nghĩa là cập nhật ~A_{X_i} = Y_i~.

Output

In ra ~Q~ dòng. Dòng thứ ~i~ in ra giá trị ~f(A)~ sau khi thực hiện cập nhật thứ ~i~.

Scoring

Trong tất cả các test:

• ~1 \le K \le N \le 2 \cdot 10^5~;

• ~1 \le Q \le 2 \cdot 10^5~;

• ~1 \le X_i \le N~;

• ~0 \le Y_i \le 10^9~.

Sample Input 1

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

Sample Output 1

5
6
8
8
15
13
13
11
1
0

Notes

Ban đầu ~A = (0, 0, 0, 0)~.

Sau cập nhật ~1~, ~A = (5, 0, 0, 0)~ nên tổng ~2~ phần tử lớn nhất là ~5~.

Sau cập nhật ~2~, ~A = (5, 1, 0, 0)~ nên kết quả là ~6~.

Sau cập nhật ~3~, ~A = (5, 1, 3, 0)~ nên kết quả là ~8~.

Các cập nhật tiếp theo được xử lý tương tự.