URI Online Judge | 1825

Anting

By Unknown BR Brazil

Timelimit: 0

A group of crazy scientists from PSGA (Pindamonhangaba's Science and Gymnastics Academy) is studying the behavior of an odd spiecies of blind ants. After years of research, they concluded that:

  1. These ants can only travel a straight path and their walking behavior is similar than that of the light. That is, whenever an ant hits a wall it "relfects" (as would a light beam when hitting a flat mirror) in such a way that the reflection angle is equal to the incidence angle;
  2. These ants only stop when encountering food and keep on moving the same way after it's eaten;
  3. The maximum an ant can travel without eating is 2 meters.

In order to prove these conclusions, the scientists built a series of sceneries to test the ants. Each scenery consists of a rectangle with dimensions of M x N meters. Each scenery has four entries, located on each of the vertices, that from now on shall be called by one of the cardinal points, as follows:

Inside the rectangle, MN amounts of food were distributed in the center of each of the 1m x 1m squares contained in the scenery. The ants are inserted into each scenery through one of the four possible entries in a path that makes a 45 degrees angle with both sides of the rectangle conected in that vertex. After walking aproximately 0.707m an ant encounters its first meal and continues following a straight line after eating it until one of the following happens:

  1. The ant hits a wall, in which case its path is reflected. The resulting path still has an angle of 45 degrees;
  2. The ant travels more than 2 meters and finds no food, in which case the poor thing dies...;
  3. The ant encounters a door, in which case it goes out of the testing area and the experiment ends.

Your mission is to write a program that predicts what's going to happen with the testing ant in each of the sceneries.

The input/output should be written in portuguese. North = Norte, South = Sul, Oeste = West, Leste = East.

Input

The input consists of a series of sceneries. For each scenery will be provided, in one line, the measurements of the rectangle, first the width M (North - West) and then the height N (North - East) (0 < m,n ≤ 100.000), the door though which the ant was inserted. A line containing a value of 0 for one of the rectangle's dimensions signals the end of the input.

Output

For each scenery, you'll have to write one line on the output file, with one of the following contents:

  1. If the ant dies, write "Dead..."
  2. On the contrary, write:
    • The percentage of food eaten during the travel. It should be written using three digits followed by the % sign, if there aren't enough digits, spaces should replace the missing digits. The percentage should be rounded to the nearest integer, in case of a tie it should be rounded down;
    • The amount of bumps the ant made on the walls of the testing area - It should be written with 10 digits, if there aren't enough digits, spaces should replace the missing digits;
    • The door through which the ant escaped the testing area.

The following image is related to the sample input/output:

Sample Input Sample Output

1 1 Norte

4 8 Norte

3 2 Sul

100000 100000 Oeste

100000 0 AnythingHereIsValid

100%         0 Sul

 25%         1 Leste

100%         3 Oeste

  0%         0 Leste