Description

A group of colonists has landed on an uncharted island, looking for that special place to stop and settle. Unfortunately, there are already natives on the island, and now it's a race to see who will be able to survive. In order to settle, a group must find food. The settlers have not learned the arts of agriculture yet, so they will invariably eat all the food and have to move on. If any groups encounter each other, they will fight to the death, since resources are scarce. Your job is to determine who will be alive or dead at the end of N turns and where they are on the island.

The island is a rectangular A x B matrix. Each square is either water, fields, or mountains. Settlers or native groups can only be located on fields (they can neither swim nor climb). Wheat grows in certain locations on the fields and is the only source of food for the groups.

Each group is assigned an identifier and has a certain number of people in it. During each year (or turn), the surviving groups (those with one or more people alive) will perform an action. The group with the lowest identifier goes first, followed by the next lowest, until all groups have had their "turn." A group can only do one of the actions listed below. To determine which action a group does, they try to do the first action. If unable to do that action, the group will try the second action, and so forth until it finds an action that it can perform. Note that a group will always be able to do one of the following actions each turn:

1. If a group is adjacent to another group, they will attack (in the case of multiple adjacent tribes, the tribe will attack the first tribe it finds in a clockwise search starting at the northern square).

At the end of each group's turn, the number of people in the group and anything they might have encountered is recalculated based on:

1. If the group ate this turn, the group will grow by 33% (rounded up) of the people that were able to eat. 5% (rounded up) of the people that did not eat will die due to starvation.

NOTE: When rounding, round the amount that will be added or subtracted from the group. Only use the cardinal points (N,S,E,W) when determining if a group is adjacent to something.

Movement: Whether a group is comprised of settlers or natives, moving on the island is highly ritualized. Each group follows a set of rules to determine which direction to move in order to find the perfect place to stop and make a (brief) home:

1. Each group remembers where it has been and determines which direction to go based on a point system. Points will be recalculated each turn as follows:

• Assign each area adjacent to the group (considering cardinal directions only) a number of points equal to the number of times the group has entered that square. Note that if a group moves to and stays in a single square for multiple turns, it has only entered the square once. Starting the simulation in a particular terrain square also counts as entering that square once.

• Since water and mountains are impassible, do not consider moving to terrain squares containing them!

Input

Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets.

A single data set has 3 components:

1. Start line - A single line, "START N", where N is a positive integer in the range 1 <= N <= 100 which indicated the number of years that must be calculated.

'.' - (period) Field, without wheat

'w' - (lower-case) Field, with wheat

'M' - (upper-case) Mountain

'W' - (upper-case) Water

'Z' - (upper-case) An integer in the range [0..n-1], where n is the number of groups on the map, and 1 <= n <= 10.

This group identifier will be unique for each group on a given map.

The number is an integer in the range [0,999], inclusive. It is only meaningful for groups (detailing how many people are left in that group), or wheat (which is the amount of wheat remaining).

Output

For each data set, there will be exactly one output set, and there will be a single blank line separating output sets.

A single output set consists of a series of lines, "GroupID Size Position YearDied", displayed in increasing order of GroupID, where:

• GroupID - The group's identification number.

START 5
W 000 W 000 W 000 W 000 W 000 W 000 W 000 W 000
W 000 W 000 . 000 . 000 2 060 . 000 w 345 W 000
W 000 . 000 . 000 . 000 . 000 . 000 . 000 W 000
W 000 1 140 . 000 . 000 0 050 . 000 . 000 W 000
W 000 W 000 . 000 M 000 M 000 . 000 . 000 W 000
W 000 W 000 w 200 M 000 M 000 . 000 3 025 W 000
W 000 W 000 . 000 . 000 . 000 . 000 . 000 W 000
W 000 W 000 . 000 . 000 . 000 . 000 . 000 W 000
W 000 W 000 . 000 w 115 w 115 . 000 . 000 W 000
W 000 W 000 W 000 W 000 W 000 W 000 W 000 W 000
END
START 3
. 000 2 100 . 000 . 000
0 100 1 050 . 000 . 000
. 000 . 000 . 000 . 000
. 000 . 000 . 000 . 000
END

0 0 (4,2) 2
1 57 (4,1)
2 43 (5,1)
3 31 (6,2)

0 72 (1,0)
1 0 (1,1) 1
2 72 (3,1)

Source

South Central USA 2001