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ụ