Zerg Rush!!!

A classic Starcraft tactic is to mass a huge swarm of cheap units such as Zerglings and throw them all at the opponent at once. When both players do this simultaneously, the clash is quick, brutal, and messy. In this problem you simulate such a battle, which may involve far more Zerglings than a real game would ever allow.

The battlefield is an $N \times N$ grid. Every Zergling occupies exactly one square, and no two Zerglings ever share a square. Each Zergling starts with $35$ hit points. Its attack value is $5$ plus the attack upgrade of the player who controls it. When one Zergling attacks another, the damage dealt equals the attacker's attack value minus the armour upgrade of the player who owns the defender, and the defender loses that many hit points. (Attack values are $5$ to $8$ and armour upgrades are $0$ to $3$, so every hit deals at least $2$ damage.)

Every turn, each Zergling independently decides what to do, using this (not very bright) algorithm:

• If at least one enemy Zergling stands in one of the $8$ squares horizontally, vertically, or diagonally adjacent to it, the Zergling attacks one of them. A Zergling attacks at most one enemy per turn.
• Otherwise, if the opposing player still has at least one Zergling anywhere on the grid, the Zergling moves. It first picks the enemy Zergling with the smallest Manhattan distance to it, then steps to whichever of its in-grid adjacent squares minimizes the Manhattan distance to that chosen enemy. The Manhattan distance between two squares is the sum of the absolute differences of their row indices and of their column indices.

Whenever a rule allows more than one direction, directions are preferred in clockwise order starting from north: north, northeast, east, southeast, south, southwest, west, northwest. North points toward the first row and west toward the first column. Concretely, a Zergling attacks the enemy found in the first such direction, and it moves in the first such direction that reaches the minimizing square. If several enemies are tied for closest when choosing a move target, the northernmost of them is chosen, and among those the westernmost.

Once every Zergling has decided, the turn resolves in exactly this order:

1. All attacks are applied simultaneously; each defender loses the total damage dealt to it this turn.
2. Every Zergling now at $0$ or fewer hit points dies and is removed from the grid.
3. Every Zergling that chose to move now moves, simultaneously, subject to two rules. First, if the target square is occupied by another Zergling that is not itself vacating that square this turn, the mover stays where it is (so a Zergling may move into a square that is being vacated, and two or more Zerglings may swap or rotate). Second, if two or more Zerglings try to move into the same square, the one in the northernmost row has priority and the others stay; among those tied in the northernmost row, the westernmost one moves and the rest stay.
4. Finally, every surviving Zergling with fewer than $35$ hit points regenerates $1$ hit point.

The input contains several test cases and ends with a case in which $N = 0$; that terminating case is not processed.

Each test case is given as follows:

• A line with the integer $N$ ($2 \le N \le 150$), the side length of the grid.
• A line with two integers between $0$ and $3$: the attack upgrade and the armour upgrade of player 1.
• A line with two integers between $0$ and $3$: the attack upgrade and the armour upgrade of player 2.
• $N$ lines describing the initial grid. A . is an empty square, a 1 is a Zergling owned by player 1, and a 2 is a Zergling owned by player 2. The first row is the north edge and the first column is the west edge.
• A line with the integer $t$ ($0 \le t \le 400$), the number of turns to simulate.

For each test case, output the grid after $t$ turns in the same format as the input grid: $N$ lines of $N$ characters each. Print one empty line between the outputs of consecutive test cases.