Farmer John muốn chụp ảnh những chú bò trên cánh đồng kỳ diệu.

Cánh đồng là một lưới gồm ~N \times N~ ô ~(1 \le N \le 500)~, mỗi ô có đúng một con bò đứng cố định.

Máy ảnh của Farmer John có thể chụp bất kỳ vùng hình vuông ~K \times K~ nào nằm hoàn toàn trong cánh đồng, với ~1 \le K \le \min(N, 25)~.

Mỗi con bò có một chỉ số sắc đẹp từ ~0~ đến ~10^6~. Độ hấp dẫn của một bức ảnh được tính bằng tổng chỉ số sắc đẹp của tất cả những con bò nằm trong vùng được chụp.

Ban đầu, chỉ số sắc đẹp của tất cả các con bò đều bằng ~0~.

Có ~Q~ lần cập nhật ~(1 \le Q \le 3 \cdot 10^4)~. Trong mỗi lần, một con bò ăn cỏ kỳ diệu và chỉ số sắc đẹp của nó tăng lên.

Yêu cầu: Sau mỗi lần cập nhật, hãy xác định độ hấp dẫn lớn nhất mà Farmer John có thể đạt được khi chụp một bức ảnh kích thước ~K \times K~.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N, K~.
• Dòng thứ hai 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~, biểu thị con bò tại hàng ~r~, cột ~c~ được cập nhật chỉ số sắc đẹp thành ~v~.
  • ~1 \le r, c \le N~
  • ~1 \le v \le 10^6~
  • Giá trị ~v~ luôn lớn hơn chỉ số sắc đẹp trước đó của con bò tại vị trí ~(r,c)~.

Dữ liệu ra

In ra ~Q~ dòng. Dòng thứ ~i~ là độ hấp dẫn lớn nhất của một bức ảnh sau lần cập nhật thứ ~i~.

Ví dụ 1

Input

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

Output

11
11
111

Giải thích

• Sau lần cập nhật thứ nhất, chọn vùng hình vuông có góc trên bên trái ~(2,2)~ và góc dưới bên phải ~(3,3)~. Tổng độ hấp dẫn là ~11 + 0 + 0 + 0 = 11~.
• Lần cập nhật thứ hai không làm thay đổi độ hấp dẫn lớn nhất.
• Sau lần cập nhật thứ ba, chọn vùng có góc trên bên trái ~(2,1)~ và góc dưới bên phải ~(3,2)~. Tổng độ hấp dẫn là ~0 + 11 + 100 + 0 = 111~.

Ví dụ 2

Input

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

Output

3
5
7

Giải thích

Chỉ có một con bò có chỉ số sắc đẹp dương, nên bức ảnh tối ưu luôn chứa con bò đó.

Giới hạn

• Subtask 1 (Test 3–6): ~N \le 50, Q \le 100~.
• Subtask 2 (Test 7–10): ~N \le 50~.
• Subtask 3 (Test 11–18): Không có ràng buộc bổ sung.