명백한 운명

문제

개척민 무리가 정착할 곳을 찾아 지도에 없던 섬에 상륙했다. 섬에는 이미 원주민이 살고 있어서, 이제 누가 살아남는지를 겨루는 경주가 시작된다. 정착하려면 먼저 식량을 구해야 한다. 개척민은 농사를 배운 적이 없어서 손 닿는 식량을 모두 먹어 치우고 다시 떠난다. 두 무리가 마주치면 자원이 모자란 탓에 죽을 때까지 싸운다. $N$ 번의 턴이 지난 뒤 어느 무리가 살아 있고 어느 무리가 죽었는지, 그리고 각 무리가 섬의 어디에 있는지 구하라.

섬은 $A \times B$ 크기의 직사각형 격자다. 각 칸은 물, 들판, 산 중 하나다. 개척민과 원주민 무리는 헤엄치지도 오르지도 못해서 들판에만 설 수 있다. 들판 일부에는 밀이 자라며, 밀은 무리가 먹을 수 있는 유일한 식량이다.

무리마다 식별 번호와 인원수가 정해져 있다. 매 해(턴)마다 살아 있는 무리, 즉 인원이 1명 이상 남은 무리가 각각 한 번씩 행동한다. 식별 번호가 가장 작은 무리부터 시작해 번호가 커지는 순서로 모든 무리가 차례를 마친다. 한 무리는 아래 행동 중 정확히 하나만 한다. 어떤 행동을 할지는 첫 번째부터 차례로 시도해서 정한다. 첫 번째를 할 수 없으면 두 번째를, 두 번째도 할 수 없으면 세 번째를 시도한다. 세 행동 중 적어도 하나는 언제나 할 수 있다.

다른 무리와 인접해 있으면 공격한다. 인접한 무리가 여럿이면 북쪽 칸에서 시작하는 시계 방향 탐색으로 가장 먼저 찾은 무리를 공격한다.
밀과 인접해 있으면 그 밀을 먹고 움직이지 않는다. 인접한 밀 칸이 여럿이면 무리의 북쪽 칸에서 시작하는 시계 방향 탐색으로 가장 먼저 만난 칸의 밀부터 먹는다. 그 칸의 밀은 무리의 인원수만큼 줄어든다. 무리의 인원이 그 칸의 밀보다 많으면 시계 방향 순서로 다음 밀 칸을 이어서 먹고, 인접한 칸에 밀이 하나도 남지 않거나 먹은 밀의 총량이 무리의 인원수와 같아질 때까지 계속한다. 밀을 다 먹은 칸은 밀 없는 보통 들판이 된다.
턴을 시작할 때 인접한 밀이 하나도 없으면 식량을 찾아 북, 동, 남, 서 중 한 칸으로 이동한다. 이동 규칙은 아래에 있다. 이동할 수 없으면 제자리에 남는다.

각 무리의 턴이 끝나면 인원수를 다시 계산한다.

이번 턴에 먹었다면 밀을 먹은 인원의 33%(올림)만큼 무리가 늘어난다. 먹지 못한 인원의 5%(올림)는 굶어 죽는다.
다른 무리를 공격했다면 자기 전투력만큼 상대의 인원을 죽인다. 전투력은 자기 인원수의 50%(올림)다. 싸우는 동안 아무도 먹지 못하므로 전투가 끝난 뒤 공격한 무리의 10%(올림)가 죽는다. 피해를 주는 쪽은 공격한 무리뿐이다. 공격당한 무리는 아직 힘이 남아 있다면 자기 차례에 반격한다.
다른 칸으로 이동했다면 굶주림과 이동의 고단함으로 인원의 10%(올림)가 죽는다.

올림은 무리에 더하거나 무리에서 빼는 인원수에 적용한다. 인접 여부는 동서남북 네 방향으로만 따진다.

이동. 개척민이든 원주민이든 섬에서 움직이는 방식은 엄격한 의식을 따른다. 각 무리는 다음 규칙으로 방향을 고른다.

무리는 자기가 지나온 자리를 기억하고 점수로 방향을 정한다. 점수는 매 턴 다시 계산한다. 무리와 인접한 각 칸에 동서남북만 따져서, 그 무리가 그 칸에 들어간 횟수만큼 점수를 매긴다. 한 칸으로 이동한 뒤 여러 턴을 머물러도 들어간 횟수는 한 번이다. 시뮬레이션을 시작한 칸도 한 번 들어간 것으로 센다. 무리는 왔던 길을 되짚기를 싫어하므로 바로 직전에 있던 칸의 점수는 위에서 구한 값의 두 배로 친다.
점수가 가장 낮은 방향으로 이동한다. 점수가 같으면 북, 동, 남, 서 순서에서 앞에 오는 방향을 고른다.

물과 산은 지나갈 수 없으므로 이동할 칸으로 아예 고려하지 않는다.

위 규칙에서 그대로 따라 나오는 세부 사항.

인원이 0이 된 무리는 즉시 지도에서 사라지고, 그 무리가 서 있던 칸은 보통 들판이 된다.
한 번도 이동한 적이 없는 무리에게는 직전에 있던 칸이 없으므로, 그 턴에는 두 배 점수를 받는 칸도 없다.
이동할 칸이 하나도 없는 무리는 제자리에 남고 아무도 죽지 않는다.

입력

입력은 최대 100개의 데이터 집합으로 이루어지며 비어 있지 않다. 각 데이터 집합은 아래 형식을 따르고, 집합 사이에 빈 줄은 없다.

데이터 집합 하나는 세 부분으로 이루어진다.

시작 줄. START N 한 줄이며, $N$ 은 시뮬레이션할 햇수로 $1 \le N \le 100$ 인 양의 정수다.
시작 지도. 시작 배치를 나타내는 지도이며, $A$ 개의 줄에 각각 $B$ 개의 칸이 적혀 있다. $A \times B$ 지도의 크기는 입력에 직접 주어지지 않지만 $A$ 와 $B$ 는 모두 1 이상 20 이하다. 한 줄 안의 칸은 공백 하나로 구분하고, 각 칸은 식별자와 숫자 한 쌍이다. 식별자는 다음 중 하나다.
- . (마침표) 밀이 없는 들판
- w (소문자) 밀이 있는 들판
- M (대문자) 산
- W (대문자) 물
- $[0, n-1]$ 범위의 정수. $n$ 은 지도에 있는 무리의 수이고 $1 \le n \le 10$ 이다. 무리 식별 번호는 한 지도 안에서 서로 다르다.
숫자는 $[0, 999]$ 범위의 정수다. 이 숫자는 무리(남은 인원수)와 밀(남은 밀의 양)에만 의미가 있다.
끝 줄. END 한 줄.

출력

데이터 집합마다 출력 집합을 정확히 하나씩 출력하고, 출력 집합 사이에는 빈 줄을 하나 넣는다.

출력 집합 하나는 GroupID Size Position YearDied 형식의 줄로 이루어지며, GroupID가 커지는 순서로 출력한다.

GroupID는 무리의 식별 번호다.
Size는 $N$ 년이 지난 뒤의 인원수다.
Position은 $N$ 년이 지난 뒤의 위치 (X,Y)다. X는 열, Y는 행이고, (0,0)은 가장 북서쪽 칸, 즉 시작 지도 첫 줄의 첫 칸이다.
YearDied는 이 무리가 죽은, 즉 인원이 0이 된 해를 나타내는 양의 정수다. $N$ 년이 끝날 때까지 살아 있는 무리는 이 항목을 출력하지 않는다.