Bình sở hữu một trang trại nông nghiệp công nghệ cao kích thước \(N \times M\) ô đất. Bình muốn chọn một vùng đất hình vuông có kích thước cố định là \(K \times K\) ô để lắp đặt hệ thống tưới tiêu tự động mới sao cho tổng sản lượng cây trồng hiện tại trong vùng hình vuông này đạt giá trị lớn nhất.

Ban đầu sản lượng của tất cả các ô đất đều bằng \(0\). Bình thực hiện \(Q\) sự kiện biến động sản lượng nông sản:

• 1 x y val: Sản lượng tại ô đất tọa độ hàng \(x\) cột \(y\) thay đổi tăng thêm một lượng là \(val\).
• 2: Bình muốn tìm tổng sản lượng cây trồng lớn nhất có thể đạt được trong một vùng hình vuông kích thước \(K \times K\) bất kỳ nằm hoàn toàn trong trang trại.

Hãy lập trình giúp Bình đưa ra quyết định lắp đặt tốt nhất.

Định dạng đầu vào

• Dòng đầu chứa bốn số nguyên dương \(N, M, K\) và \(Q\) (\(1 \le K \le N, M \le 100\), \(1 \le Q \le 500\)).
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một sự kiện. Nếu sự kiện là loại 1, dòng chứa 1 x y val (\(1 \le x \le N, 1 \le y \le M, 0 \le val \le 10^6\)). Nếu sự kiện là loại 2, dòng chỉ chứa duy nhất số 2.

Định dạng đầu ra

• Với mỗi sự kiện loại 2, in ra tổng sản lượng cây trồng lớn nhất tìm được trên một dòng.

Ví dụ

Input:

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

Output:

18