Chụp Ảnh

Farmer John muốn chụp ảnh các con bò trong lưới $N\times N$. Máy ảnh chụp được vùng vuông $K\times K$.

Ban đầu, mỗi ô có giá trị đẹp bằng $0$. Sau mỗi lần cập nhật giá trị đẹp của một con bò, hãy tìm độ hấp dẫn lớn nhất — tức là tổng giá trị đẹp lớn nhất trong tất cả các vùng $K\times K$ có thể.

Dữ liệu vào

• Dòng 1: Hai số nguyên $N$ và $K$
• Dòng 2: Số nguyên $Q$ — số lần cập nhật
• $Q$ dòng tiếp theo, mỗi dòng gồm 3 số nguyên $r$, $c$, $v$: đặt giá trị đẹp của ô $(r,c)$ thành $v$

Dữ liệu ra

• $Q$ dòng, mỗi dòng là độ hấp dẫn lớn nhất sau lần cập nhật tương ứng.

Ràng buộc

• $1\le N\le 500$
• $1\le K\le min(N,25)$
• $1\le Q\le 3\times {10}^4$
• $1\le v\le {10}^6$
• $1\le r,c\le N$

Ví dụ