Time limit per test: 0.25
second(s)

Memory limit: 65536 kilobytes

Memory limit: 65536 kilobytes

input: standard

output: standard

output: standard

Peter has a boat. He loves to use it for fishing on the Berland Lake. But today an accident happen with him. A huge fish ate the hook, and when Peter tried to take the fish out of the lake, he suddenly discovered that the fish was stronger. Unfortunately Peter was unable to stay on the board and he fell down into the water. But he did not want to lose such a catch. So the fish took him somewhere...

The Peter is now somewhere inside the lake and lost his boat and his rod. Luckily, Peter knows each bermeter of this lake (bermeter is the length measurement unit in Berland). You will help Peter to create the plan to save himself.

The lake is a rectangle of

- When Peter is in the center of some cell, his real velocity is the sum of the vectors of the velocity of the flow and Peter's movement vector. He moves with this velocity until he reaches the center of some other cell, where his new velocity will be calculated independently of the previous velocity. The velocity could not be changed in any place other than the center of some cell.
- For each cell you know the flow velocity, it can be one of the following five vectors: 1: (0, -1), 2: (0, 1), 3: (1, 0), 4: (-1, 0), 0: (0, 0). All velocities are in bermeters per minute. Peter's movement vector also is chosen among these five vectors, and he can change it any time when he is in the center of some cell. E. g. if the flow velocity is (0, -1) and the Peter's movement vector is (1, 0) then the resulting velocity will be (1, -1), i. e. Peter will move diagonally. Note that Peter may stay in the center of any cell during any period of time (may be non-integer amount of minutes) by selecting movement vector opposite to the flow speed. If Peter moves with the same vector as the flow, he will reach the center of the next cell in half a minute.
- The boat moves according to the same laws as Peter, but the boat's movement speed is always zero.
- Peter is saved when he is in the same point as the boat (it is not neccessary to reach the center of any cell) or if he reaches the shore of the lake. The boat can also reach the shore, if it happens, the boat stops there.

SOS".

sample input |
sample output |

4 6 222222 444444 444444 111111 5 3 6 2 |
2.00 |

sample input |
sample output |

3 2 00 32 11 1 2 2 3 |
0.67 |

sample input |
sample output |

3 5 32240 33442 31140 2 2 5 2 |
SOS |

Online Contester Team © 2002 - 2010. All rights reserved. |