폭풍 속의 비명

학창 시절에 배웠겠지만, 인류는 적어도 약 7000년 전에 맥주 양조를 시작했다. 그때부터 소비된 맥주의 총량은 어마어마할 것이고, 앞으로 다가올 천 년 동안 소비 속도가 줄어들지는 않을 것이다.

이 사실을 기념하기 위해, 맥주 양조와는 겉보기에 아무 관련이 없는 게임을 하나 구현해 보자. 하지만 성공적으로 구현하고 나면, 마치 하루치 맥주를 조금 넘겨 마신 것처럼 어지러워질지도 모른다.

게임은 서로 다른 종류의 정사각형 타일로 이루어진 직사각형 M × N 격자에서 진행된다.

동물과 먹이

격자 위에는 여러 마리의 동물이 있고, 각 동물은 정확히 한 타일을 차지한다.

풀은 자라고, 양은 풀을 먹고, 늑대는 양을 먹으며, 늑대와 양 모두 굶어 죽을 수 있다.

턴과 동물의 행동

각 턴은 다음 순서로 진행된다.

1. 격자 위의 모든 동물이 이동한다. 늑대는 동쪽(오른쪽)으로 이웃한 타일로 이동한다. 이동이 불가능하면 늑대는 자기 행의 가장 서쪽 타일로 이동한다. 양은 남쪽(아래)으로 이웃한 타일로 이동한다. 이동이 불가능하면 양은 자기 열의 가장 북쪽 타일로 이동한다.
2. 늑대와 양이 같은 타일에 있으면 늑대가 양을 먹고, 그 타일은 사체가 있는 흙 타일이 된다.
3. 양이 풀이 있는 흙 타일에 있으면 양이 풀을 먹고, 그 타일은 흙 타일이 된다.
4. 늑대가 현재 턴을 포함한 지난 10턴 동안 아무것도 먹지 않았으면 늑대는 죽고, 그 타일은 사체가 있는 흙 타일이 된다.
5. 양이 현재 턴을 포함한 지난 5턴 동안 아무것도 먹지 않았으면 양은 죽고, 그 타일은 사체가 있는 흙 타일이 된다.

타일의 종류와 변화

타일에는 세 종류가 있다. 타일의 종류는 게임이 진행되면서 바뀔 수 있다.

1. 흙 타일: 게임이 시작된 후 3턴이 지나거나, 타일이 흙 타일이 된 후 3턴이 지나면 풀이 있는 흙 타일이 된다.
2. 풀이 있는 흙 타일: 양이 풀을 먹으면 그 타일은 즉시 흙 타일이 된다. 3턴 후에 그 타일에서 풀이 다시 자란다.
3. 사체가 있는 흙 타일: 어떤 타일에서 동물이 죽으면 그 타일은 종류와 관계없이 즉시 사체가 있는 흙 타일이 된다. 동물은 이 타일로 이동할 수 있지만, 이 타일에서는 풀이 다시 자라지 않는다. 게임이 진행되면서 이 타일에 사체가 더 쌓일 수 있다.

입력의 첫 줄에는 세 정수 T, N, M (1 ≤ T ≤ 100, 1 ≤ M, N ≤ 20)이 주어진다. T는 턴의 수, M은 격자의 행 수, N은 격자의 열 수이다. 다음 M개 줄에는 각각 N개의 문자가 주어진다. 문자는 타일의 종류를 나타낸다.

• . (마침표 문자)는 흙 타일을 나타낸다.
• S는 양이 있는 흙 타일을 나타낸다.
• W는 늑대가 있는 흙 타일을 나타낸다.

T번째 턴이 끝난 후 격자의 상태를 나타내는 M개 줄을 각각 N개의 문자로 출력한다. 타일 위에 동물이 있으면 다음을 출력한다.

• 늑대가 있는 타일은 W
• 양이 있는 타일은 S

그렇지 않으면 다음을 출력한다.

• 사체가 있는 흙 타일은 *
• 풀이 있는 흙 타일은 #
• 흙 타일은 . (마침표 문자)