시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 119 49 37 63.793%

문제

생명 게임은 수학자 콘웨이(John Horton Conway)가 창안한 게임으로, 바둑판 모양의 격자에 '생명'을 배치하고 그 변화를 관찰하는 게임이다.

<그림1> 자리를 바꾸면서 무한히 움직이는 패턴의 한 예. 출처) 네이버 지식백과

준표는 콘웨이가 창안한 생명 게임에서 사소한 조건을 바꿔 새로운 규칙의 생명 게임을 제안 해보았다.

<그림2>

바둑판의 각 칸은 주위의 영향을 받는데, 주위란 <그림2>에서 색칠한 영역과 같이 현재 칸을 중심으로 둔 한 변의 길이가 (2K + 1) 인 정사각형에서 현재 칸을 제외한 영역을 말한다.

바둑판의 각 칸은 주위에 몇 개의 생명이 존재하는지에 따라 다음 상황이 아래와 같이 결정된다.

  1. 생존 : 만약 현재 칸에 생명이 있고, 주위에 a개 이상 b개 이하의 생명이 있다면 현재 칸의 생명은 다음 단계에 살아남는다.
  2. 고독 : 만약 현재 칸에 생명이 있고, 주위에 a개 미만의 생명이 있다면 현재 칸의 생명은 외로워서 죽는다.
  3. 과밀 : 만약 현재 칸에 생명이 있고, 주위에 b개 초과의 생명이 있다면 현재 칸의 생명은 과밀로 죽는다.
  4. 탄생 : 만약 현재 칸에 생명이 없고, 주위에 a개 초과 b개 이하의 생명이 있다면 다음 단계에서 현재 칸에 생명이 생긴다.

생명은 바둑판을 벗어난 영역에서는 생존할 수 없다.

준표는 N×M 크기의 바둑판에 생명을 뿌리고, T시간 뒤의 생명을 관찰하고자 한다.

입력

첫줄에는 바둑판의 세로길이, 가로길이를 나타내는 두 정수 NM, 준표가 바둑판을 관찰하고자 하는 시간 T가 주어진다.

두번째 줄에는 주위의 기준이 되는 정수 K, 각 칸의 다음 상황을 결정하는 정수 a, b가 주어진다.

다음 N개의 줄에 걸쳐 바둑판의 처음 상태가 주어진다. 각 줄은 길이 M의 문자열로 생명이 있는 칸은 '*', 빈칸은 '.'로 주어진다.

출력

N개의 줄에 걸쳐 바둑판의 상태를 출력한다. 각 줄은 길이 M의 문자열로 생명이 있는 칸은 '*', 빈칸은 '.'로 출력한다.

제한

  • 1 ≤ N, M ≤ 100
  • 1 ≤ T ≤ 300
  • 0 ≤ a, b < (2×K+1)2

서브태스크 1 (100점)

  • K = 1

서브태스크 2 (40점)

  • 1 ≤ K ≤ max(N, M)

예제 입력 1

6 6 7
1 2 3
.*....
..*...
***...
......
......
......

예제 출력 1

......
......
..*...
...**.
..**..
......

채점

  • 예제는 채점하지 않는다.