Robot

The Robot Moving Institute uses a robot in their store to transport items, and the robot should spend the minimum time possible travelling from one place to another.

The robot moves only along straight tracks. All tracks form a rectangular grid, and neighbouring tracks are 1 meter apart. The store is an $N \times M$ meter rectangle entirely covered by this grid, and the track closest to any side of the store is exactly 1 meter from it.

The robot has a circular shape with a diameter of 1.6 meters, and the track passes through the center of the robot. The robot always faces north, south, west, or east; the tracks run south-north and west-east. The robot can move only in the direction it faces, and it can change that direction at any track crossing. Initially the robot stands at a track crossing.

Obstacles occupy $1\text{m} \times 1\text{m}$ squares on the ground, and each obstacle lies within a single square bounded by tracks.

The robot is controlled by two commands:

• GO takes one integer parameter $n \in {1, 2, 3}$. On receiving it, the robot moves $n$ meters in the direction it faces.
• TURN takes one parameter, either left or right. On receiving it, the robot rotates its orientation by 90° in the indicated direction.

Executing each command takes one second.

Write a program that determines the minimum time in which the robot can move from a given starting point to a given destination.

The input consists of blocks of lines. The first line of each block contains two integers $M \le 50$ and $N \le 50$ separated by one space. Each of the next $M$ lines contains $N$ numbers (each 0 or 1) separated by spaces, where 1 marks an obstacle and 0 an empty square. (The tracks lie between the squares.)

The block ends with a line containing four positive integers $B_1$ $B_2$ $E_1$ $E_2$, each followed by one space, and then a word giving the robot's starting orientation. $B_1, B_2$ are the coordinates of the starting square, at whose north-west corner the robot is placed. $E_1, E_2$ are the coordinates of the destination square, at whose north-west corner the robot must arrive. The orientation at the destination is not prescribed.

Coordinates are of the (row, column) type: the most north-west square is (0, 0) and the most south-east square is $(M-1, N-1)$. The orientation is one of north, west, south, or east.

The last block consists of a single line with $M = 0$ and $N = 0$.

For every block except the last, output one line, in the same order as the input blocks. Each line contains the minimum number of seconds in which the robot can reach the destination from the starting point. If no path from the start to the destination exists, the line contains -1.