Giải bài trực tuyến

Từ đề thi tin học trẻ toàn quốc bảng C, 2012:

"Trò chơi “Bi đổi mầu” là trò chơi đối kháng gồm hai người chơi trên lưới hình chữ nhật mxn ô vuông. Các dòng được đánh số từ 1 đến m từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái qua phải. Ô nằm ở vị trí dòng i và cột j  của lưới được gọi là ô (i,j) và khi đó, i được gọi là toạ độ dòng còn j được gọi là toạ độ cột của ô này.

Tại mỗi lượt chơi, mỗi người trong hai người chọn một hình vuông kích thước p × p  của mình rồi bí mật viết ra một mảnh giấy hai số là tọa độ góc trái trên của hình vuông mà mình chọn. Sau đó cả hai công bố hình vuông của mình. Những viên bi nằm trong hình vuông mà hai người chơi chọn sẽ bị đổi màu, trừ những viên bi nằm trong cả hai hình vuông. Xét trường hợp bi của bạn là màu xanh."

+Gọi Sum(x,y,i,j) với 1<=i,x<=m-p+1 và 1<=j,y<=n-p+1 số bi xanh có được trên ma trận sau khi chọn hình vuông pxp có góc trên trái là (x,y) và đối phương chọn hình vuông pxp có góc trên trái là (i,j).

+Gọi Msum(x,y) là min(sum(x,y,i,j)) với mọi 1<=i<=m-p+1 và 1<=j<=n-p+1.

Yêu cầu: Tính tất cả Msum(x,y) với mọi 1<=x<=m-p+1 và 1<=y<=n-p+1.

Input

Dòng đầu tiên chứa số m,n,p (1<=m,n<=100, 1<=p<=min(m,n)).

m dòng sau: mỗi dòng chứ kí tự ‘0’ hoặc ‘1’ hoặc ‘2’ – ‘0’ tương ứng với ô không có bi, ‘1’ tương ứng với ô có bi xanh, ‘2’ tương ứng với ô có bi đỏ.

Output

Gồm m-p+1 dòng, mỗi dòng i chứa n-p+1 số nguyên là Msum(i,1),  Msum(i,2), …, Msum(i,n-p+1).

Example

Input:
6 8 5
00022112
20221022
01102101
01021122
02211112
21000001

Output:
12 13 12 16
14 15 14 16
 
33.33% số test với m,n <= 10.
33.33% số test tiếp theo với m,n<=50.
33.33% số test tiếp theo với m,n <= 100.