파리채

한 변이 K인 정사각형 파리채를 놓아 테두리를 제외한 내부 파리가 가장 많아지는 위치를 찾아 개수와 테두리를 그린 그림을 출력합니다.

쉬움3누적 합행렬완전 탐색면접 대비아직 제출이 없습니다시간 제한1초메모리 제한64 MB

문제

마린은 시간이 나면 창밖을 내다본다. 그 창문에는 파리 몇 마리가 앉아 먼 곳을 바라보고 있다. 마린은 정사각형 파리채를 들고 와서, 한 번 내리쳐 파리를 최대 몇 마리까지 잡을 수 있을지 궁금해졌다.

창문 사진의 크기는 R×SR \times S 픽셀이고, 파리채의 한 변 길이는 KK 픽셀이다. 한 번 내리쳐 잡을 수 있는 파리의 최대 마리 수를 구하고, 그렇게 잡을 수 있는 파리채 위치 하나를 사진 위에 표시하라.

입력

첫째 줄에 사진의 크기와 파리채의 한 변 길이를 나타내는 세 정수 RR, SS, KK가 주어진다 (3KR1003 \le K \le R \le 100, KS100K \le S \le 100).

다음 RR개 줄에는 각각 SS개의 문자가 주어져 창문 사진을 나타낸다. 파리가 앉은 픽셀은 *, 빈 픽셀은 .이다. 파리채로 잡을 수 있는 파리가 적어도 한 마리 있다.

출력

첫째 줄에 한 번 내리쳐 잡을 수 있는 파리의 최대 마리 수를 출력한다.

이어서 RR개 줄에 파리채 위치를 표시한 사진을 출력한다. 파리채의 가로 변은 -, 세로 변은 |, 네 모서리는 +로 나타내며, 이 문자는 원래 픽셀 위에 덮어 쓴다.

파리채는 창문 안에 완전히 들어가야 한다. 변 위에 있는 파리는 날아갈 시간이 충분하므로, 파리채 내부에 엄격히 들어 있는 파리만 잡힌다. 행과 열을 00부터 셀 때 왼쪽 위 모서리가 (i,j)(i, j)인 파리채는 행 i+1i+1부터 i+K2i+K-2까지, 열 j+1j+1부터 j+K2j+K-2까지에 있는 파리를 잡는다.

최대 마리 수를 잡는 위치가 여럿이면 왼쪽 위 모서리의 행 번호가 가장 작은 위치를 표시하고, 그런 위치도 여럿이면 그중 열 번호가 가장 작은 위치를 표시한다.