Farmer John đang ngắm đàn bò của mình trên một cánh đồng kỳ diệu và muốn chụp ảnh các tập con của đàn bò.

Cánh đồng có thể được xem là một lưới \(N\times N\) (\(1\leq N\leq 500\)), với đúng một chú bò đứng yên tại mỗi vị trí. Máy ảnh của Farmer John có thể chụp một hình vuông \(K\times K\) bất kỳ nằm trong cánh đồng (\(1\leq K\leq \min(N,25)\)).

Tại mọi thời điểm, mỗi chú bò có một giá trị vẻ đẹp từ \(0\) đến \(10^6\). Chỉ số hấp dẫn của một bức ảnh là tổng giá trị vẻ đẹp của những chú bò có trong ảnh.

Ban đầu, giá trị vẻ đẹp của mọi chú bò đều bằng \(0\), vì vậy chỉ số hấp dẫn của mọi bức ảnh lúc đầu đều bằng \(0\).

Tại \(Q\) thời điểm (\(1\leq Q\leq 3\cdot 10^4\)), giá trị vẻ đẹp của một chú bò sẽ tăng thêm một số nguyên dương do ăn loại cỏ kỳ diệu được trồng trên cánh đồng của Farmer John.

Farmer John muốn biết chỉ số hấp dẫn lớn nhất của một bức ảnh mà ông có thể chụp sau mỗi lần trong \(Q\) lần cập nhật.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\).

Dòng tiếp theo chứa số nguyên \(Q\).

Mỗi dòng trong \(Q\) dòng tiếp theo chứa ba số nguyên \(r\), \(c\) và \(v\), lần lượt là hàng, cột và giá trị vẻ đẹp mới (\(1\leq r,c\leq N\), \(1\leq v\leq 10^6\)). Đảm bảo rằng giá trị vẻ đẹp mới lớn hơn giá trị vẻ đẹp tại vị trí đó trước lần cập nhật.

Dữ liệu ra

In ra \(Q\) dòng, tương ứng với chỉ số hấp dẫn lớn nhất của một bức ảnh sau mỗi lần cập nhật.

Ví dụ

4 2
3
2 2 11
3 4 3
3 1 100

11
11
111

3 1
3
2 2 3
2 2 5
2 2 7

3
5
7

Phân nhóm

• Input 3–6: \(N\leq 50\), \(Q\leq 100\).
• Input 7–10: \(N\leq 50\).
• Input 11–18: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 1, Bronze, bài Photoshoot. Tác giả: Brian Law và Cici Liu.
https://usaco.org/index.php?page=viewproblem2&cpid=1541