인공 분쟁 (Artificial Strife)

문제

콘웨이의 라이프 게임(Conway's Game of Life)은 정사각형 격자 위의 세포들에 대해 진행하는 시뮬레이션이다. 각 세포는 살아 있거나 죽어 있으며, 매 턴의 상태는 이전 턴으로부터 계산된다. 즉, $n+1$턴에서 어떤 세포의 상태는 $n$턴에서의 자기 자신의 상태와 그 세포를 둘러싼 여덟 개 이웃 세포의 상태에 의해 결정된다. 표준 라이프 게임에서 살아 있는 세포는 살아 있는 이웃이 두 개 또는 세 개이면 계속 살아 있고, 죽어 있는 세포는 살아 있는 이웃이 정확히 세 개이면 살아난다. 그 외의 경우에는 세포가 죽거나 죽은 채로 남는다. 아래 그림은 글라이더(glider)라고 불리는 단순하지만 의외로 복잡한 구조의 여러 세대를 보여 준다:

   0       1       2       3       4
....... ....... ....... ....... .......
....... ...A... ..AA... ..AA... .AAA...
..AAA.. ..AA... ..A.A.. .AA.... .A.....
..A.... ..A.A.. ..A.... ...A... ..A....
...A... ....... ....... ....... .......
....... ....... ....... ....... .......

네 턴이 지나면 구조 전체가 위로 한 칸, 왼쪽으로 한 칸 이동한 것을 알 수 있다. 라이프 게임에는 이보다 훨씬 복잡한 구조가 많이 있으며, 격자 위에 (매우, 매우 느린) 튜링 기계를 만들거나 라이프 게임 자체를 라이프 게임 위에서 시뮬레이션하는 것도 가능하다.

원래 라이프 게임의 규칙은 23/3으로 표기한다. 즉, 어떤 세포는 $n$턴에 살아 있는 이웃이 두 개 또는 세 개이면 $n+1$턴에도 살아 있고, 죽어 있는 세포는 살아 있는 이웃이 정확히 세 개이면 살아난다. 같은 표기법으로 나타낼 수 있는 다른 "콘웨이류" 규칙도 많다. 예를 들어 /234(모든 살아 있는 세포는 죽지만, 죽어 있는 세포는 이웃이 두 개, 세 개, 또는 네 개이면 살아난다)와 같은 규칙도 완전히 유효하며(그리고 꽤 흥미롭다), "탄생" 값이 없는 규칙도 유효하지만 (당연히) 지루하다. 당신의 목표는 이런 규칙 여러 개를 같은 격자 위에서 동시에 시뮬레이션하는 것이다.

하나의 격자 위에서 둘 이상의 규칙이 동작하므로 몇 가지 명확히 할 점이 있다:

각 세포는 한 종(species, 특정 알파벳 문자로 표현되는 규칙)의 세포 하나에만 점유될 수 있다.
어떤 종의 다음 상태를 계산할 때는 같은 종의 세포만 이웃으로 센다.
둘 이상의 종이 같은 위치에 살아 있는 세포를 두려 할 때의 충돌은 다음과 같이 해결한다:
1. 정확히 한 종만 그 자리에 살아 있는 세포를 두고 나머지는 모두 죽은 채로 두면, 그 종의 살아 있는 세포를 둔다.
2. 둘 이상의 종이 그 자리에 살아 있는 세포를 두려 하면, 알파벳 순서상 가장 앞선 문자의 종이 이긴다. (예를 들어 종 B와 종 D가 모두 그 자리에 살아 있는 세포를 두려 하면, 그 세포는 종 B가 된다.)
격자는 절대로 살아날 수 없는 무한히 많은 죽은 세포로 둘러싸여 있다고 가정한다.

주어진 턴 수만큼 시뮬레이션을 실행한 뒤, 각 종의 최대 개체 수와 최소 개체 수를 보고하라.

입력

입력의 첫 줄에는 시뮬레이션의 개수를 나타내는 정수 $n$이 주어진다. 각 시뮬레이션의 첫 줄에는 세 정수 $X$ $Y$ $S$ ($1 \le X, Y \le 50$; $1 \le S \le 26$)가 주어지며, $X$와 $Y$는 각각 격자의 너비와 높이, $S$는 격자 위에 등장하는 종의 수이다. 이어지는 $Y$개의 줄은 0턴에서의 격자를 나타낸다('.'은 죽은 세포, 각 대문자는 해당 종의 살아 있는 세포이다). 그다음 $S$개의 줄은 각 종의 규칙을 위에서 설명한 표기법으로 주며, 첫 줄이 종 A, 둘째 줄이 종 B, …에 해당한다. 시뮬레이션의 마지막 줄은 시뮬레이션할 턴 수를 나타내는 정수 $T$이다.

출력

각 시뮬레이션에 대해 먼저 "Simulation #N"을 출력한다. 여기서 N은 1부터 시작하는 시뮬레이션 번호이다. 그다음 종마다 한 줄씩 $S$개의 줄을 "Species C: At most M live, at least L live." 형식으로 출력한다. 여기서 C는 종의 문자(A부터 시작), M은 (0턴을 포함한) 어떤 턴에서든 살아 있던 해당 종의 최대 개수, L은 (0턴을 포함한) 어떤 턴에서든 살아 있던 해당 종의 최소 개수이다.

힌트

아래 그림은 두 번째 예제 시뮬레이션의 초기 상태와 그 뒤로 이어지는 네 개의 상태를 보여 준다:

  0     1     2     3     4
..A.. ..... ..A.. ..... ..A..
..A.. .AAA. ..A.. .AAA. ..A..
..A.. ..... ..A.. ..B.. ..A..
..... ..B.. .BBB. .B.B. .B.B.
.BBB. .BBB. .BBB. .B.B. .B.B.

4턴에서 종 A가, 그대로 두었다면 종 B로 남았을 세포를 차지하는 것에 주목하라.