Manifest Destiny

A group of colonists has landed on an uncharted island, looking for a place to stop and settle. Natives already live there, so now it is a race to see who survives. To settle, a group has to find food. The settlers never learned farming, so they eat everything within reach and then have to move on. When two groups meet they fight to the death, because resources are scarce. Work out which groups are alive and which are dead after $N$ turns, and where each one stands on the island.

The island is a rectangular $A \times B$ matrix. Each square is water, field, or mountain. Settler and native groups can only stand on fields, since they can neither swim nor climb. Wheat grows on some of the fields and is the only food a group can eat.

Every group has an identifier and a number of people. During each year (turn) the surviving groups, meaning those with one or more people alive, each take one action. The group with the lowest identifier goes first, then the next lowest, until every group has taken its turn. A group performs exactly one of the actions below. To decide which one, it tries the first action; if it cannot do that one it tries the second, and if that fails too it tries the third. At least one of the three is always possible.

1. If the group is next to another group, it attacks. When several groups are adjacent, it attacks the first one found by a clockwise search that starts at the square to the north.
2. If the group is next to wheat, it eats the wheat and does not move. When several wheat squares are adjacent, the first wheat eaten is the one found first by a clockwise search that starts at the square to the north of the group. The wheat on that square drops by the number of people in the group. If the group has more people than that square has wheat, the next wheat square in clockwise order is eaten as well, and this continues until no adjacent square holds wheat any more or the total wheat consumed equals the size of the group. A square whose wheat is completely eaten becomes an ordinary field.
3. If no wheat was adjacent at the start of the turn, the group searches for food by moving one square north, east, south, or west. The movement rules are below. If it cannot move, it stays where it is.

At the end of each group's turn its size is recomputed.

1. If the group ate this turn, it grows by 33% (rounded up) of the people who were able to eat. 5% (rounded up) of the people who did not eat starve to death.
2. If the group attacked another group, it kills a number of people equal to its strength. Strength is 50% (rounded up) of its own population. Since nobody eats while fighting, 10% (rounded up) of the attacking group dies once the fighting is over. Only the attacker deals damage. The group that was attacked has to wait for its own turn to strike back, if it still can.
3. If the group moved to another square, 10% (rounded up) of its people die from hunger and the strain of travel.

Rounding applies to the amount added to or subtracted from the group. Adjacency uses the four cardinal directions only.

Movement. Settlers and natives alike move in a highly ritualized way. Each group follows these rules to pick a direction.

1. A group remembers where it has been and picks a direction from a point score. The scores are recomputed every turn. Give each square adjacent to the group, cardinal directions only, a number of points equal to how many times the group has entered that square. A group that moves into a square and then stays there for several turns has still entered it only once. The square a group starts the simulation on counts as entered once. Groups hate doubling back, so the square the group came from most recently is worth twice the points computed above.
2. The group moves in the direction with the lowest score. Ties go to whichever tied direction comes first in this list: north, east, south, west.

Water and mountains cannot be crossed, so never consider moving onto them.

Details that follow from the rules above.

• A group whose size reaches 0 leaves the map at once, and the square it stood on becomes an ordinary field.
• A group that has never moved has no previous square, so nothing gets the doubled score on that turn.
• A group with no square to move into stays put and loses nobody.

The input holds a non-empty series of up to 100 data sets. Each data set follows the format below, and no blank lines separate data sets.

A single data set has three parts.

1. Start line. One line, START N, where $N$ is a positive integer with $1 \le N \le 100$ giving the number of years to simulate.

2. Starting map. The map of the starting position, given as $A$ lines of $B$ terrain squares each. The size of the $A \times B$ map is not stated in the input, but both $A$ and $B$ are between 1 and 20 inclusive. Terrain squares on a line are separated by a single space, and each square is a pair, an identifier and a number. The identifier is one of the following.

   • . (period) field without wheat
   • w (lower case) field with wheat
   • M (upper case) mountain
   • W (upper case) water
   • an integer in $[0, n-1]$, where $n$ is the number of groups on the map and $1 \le n \le 10$. Group identifiers are distinct within a map.

   The number is an integer in $[0, 999]$. It only means something for a group, where it is how many people are left, and for wheat, where it is how much wheat remains.

3. End line. One line, END.

Print exactly one output set per data set, with a single blank line between output sets.

An output set is a series of lines GroupID Size Position YearDied, printed in increasing order of GroupID.

• GroupID is the group's identification number.
• Size is the size of the group after $N$ years.
• Position is the position (X,Y) of the group after $N$ years, where X is the column and Y is the row, and (0,0) is the most north-west square, the first terrain square on the first line of the starting map.
• YearDied is the year (turn) in which the group died, meaning its size fell to 0, written as a positive integer. A group still alive after $N$ years has no such field.