Zerg Rush!!!

스타크래프트의 고전적인 전술 하나는 저글링처럼 값싼 유닛을 잔뜩 모아 한꺼번에 상대에게 들이미는 것입니다. 두 플레이어가 동시에 이 전략을 쓰면 전투는 순식간에, 그리고 처참하게 끝납니다. 이 문제에서는 실제 게임에서는 허용되지 않을 만큼 많은 저글링이 등장할 수 있는 이런 난전을 시뮬레이션합니다.

전장은 $N \times N$ 격자입니다. 모든 저글링은 정확히 한 칸을 차지하며, 두 저글링이 같은 칸에 있는 일은 없습니다. 각 저글링의 초기 체력은 $35$입니다. 공격력은 $5$에 그 저글링을 조종하는 플레이어의 공격 업그레이드를 더한 값입니다. 한 저글링이 다른 저글링을 공격하면, 입히는 피해는 (공격하는 저글링의 공격력) $-$ (공격받는 저글링을 소유한 플레이어의 방어 업그레이드)이며, 공격받은 저글링은 그만큼 체력을 잃습니다. (공격력은 $5$부터 $8$까지, 방어 업그레이드는 $0$부터 $3$까지이므로 모든 공격은 최소 $2$의 피해를 줍니다.)

매 턴마다 각 저글링은 다음의 (그리 똑똑하지 않은) 규칙으로 각자 행동을 결정합니다.

• 가로·세로·대각선으로 인접한 $8$개 칸 중 하나라도 적 저글링이 있으면, 그중 하나를 공격합니다. 한 저글링은 한 턴에 최대 한 명만 공격합니다.
• 그렇지 않고 상대 플레이어의 저글링이 격자 어딘가에 아직 하나라도 남아 있으면, 저글링은 이동합니다. 먼저 자신과의 맨해튼 거리가 가장 작은 적 저글링을 하나 고르고, 격자 안에 있는 인접 칸 중 그 적과의 맨해튼 거리를 최소로 만드는 칸으로 이동합니다. 두 칸 사이의 맨해튼 거리는 행 번호 차이의 절댓값과 열 번호 차이의 절댓값의 합입니다.

어떤 규칙이 둘 이상의 방향을 허용할 때는, 북쪽에서 시작해 시계 방향 순서로 우선합니다: 북, 북동, 동, 남동, 남, 남서, 서, 북서. 북쪽은 첫 번째 행을, 서쪽은 첫 번째 열을 향합니다. 즉 저글링은 이 순서에서 가장 먼저 적이 있는 방향의 적을 공격하고, 최소 거리 칸에 도달하는 가장 먼저 오는 방향으로 이동합니다. 이동 목표로 삼을 가장 가까운 적이 여럿이면 그중 가장 북쪽에 있는 적을, 다시 그중 가장 서쪽에 있는 적을 선택합니다.

모든 저글링이 결정을 마치면, 턴은 정확히 다음 순서로 처리됩니다.

1. 모든 공격을 동시에 적용합니다. 각 피격 저글링은 이번 턴에 받은 피해의 합만큼 체력을 잃습니다.
2. 체력이 $0$ 이하가 된 저글링은 모두 죽어 격자에서 제거됩니다.
3. 이동을 선택한 저글링이 두 규칙에 따라 동시에 이동합니다. 첫째, 목표 칸에 이번 턴에 그 칸을 비우지 않는 다른 저글링이 있으면, 이동하려던 저글링은 제자리에 머뭅니다(따라서 이번 턴에 비워지는 칸으로는 들어갈 수 있으며, 둘 이상의 저글링이 서로 자리를 바꾸거나 회전할 수 있습니다). 둘째, 둘 이상의 저글링이 같은 칸으로 이동하려 하면, 가장 북쪽 행에 있는 저글링이 우선하고 나머지는 머뭅니다. 가장 북쪽 행에서 여럿이 겹치면 그중 가장 서쪽의 저글링만 이동하고 나머지는 머뭅니다.
4. 마지막으로, 살아남은 저글링 중 체력이 $35$ 미만인 저글링은 모두 체력을 $1$ 회복합니다.

입력은 여러 개의 테스트 케이스로 이루어지며, $N = 0$인 케이스로 끝납니다. 이 종료 케이스는 처리하지 않습니다.

각 테스트 케이스는 다음과 같이 주어집니다.

• 격자의 한 변 길이인 정수 $N$ ($2 \le N \le 150$)이 한 줄에 주어집니다.
• $0$ 이상 $3$ 이하의 정수 두 개, 즉 플레이어 1의 공격 업그레이드와 방어 업그레이드가 한 줄에 주어집니다.
• $0$ 이상 $3$ 이하의 정수 두 개, 즉 플레이어 2의 공격 업그레이드와 방어 업그레이드가 한 줄에 주어집니다.
• 초기 격자를 나타내는 $N$개의 줄이 이어집니다. .은 빈 칸, 1은 플레이어 1의 저글링, 2는 플레이어 2의 저글링입니다. 첫 번째 행이 북쪽 가장자리, 첫 번째 열이 서쪽 가장자리입니다.
• 시뮬레이션할 턴 수인 정수 $t$ ($0 \le t \le 400$)가 한 줄에 주어집니다.

각 테스트 케이스에 대해, $t$턴이 지난 뒤의 격자를 입력 격자와 같은 형식($N$개의 줄, 각 줄에 $N$개의 문자)으로 출력합니다. 연속한 두 테스트 케이스의 출력 사이에는 빈 줄을 하나 출력합니다.