Robot

Many factories use robots that move along fixed tracks. The robot in this factory always faces one of four directions: east, west, south, or north. It can only move forward in the direction it is facing. The controller supports two kinds of commands.

• Command 1. Go k: k is one of 1, 2, or 3. The robot moves forward k cells in its current direction.
• Command 2. Turn dir: dir is left or right. The robot turns 90 degrees in that direction.

The track layout in the factory is given as a rectangular grid of 0s and 1s. A 0 means the cell has a track and can be entered by the robot, while a 1 means the cell cannot be entered. If the robot moves forward by multiple cells with one command, every cell it passes through must have a track.

The figure below shows a situation where the robot starts at (4, 2) facing south and must arrive at (2, 4) facing east. In that situation, 9 commands are enough.

Given the robot's current position and direction, and the required destination position and direction, write a program that finds the minimum number of commands needed to reach the required state.

The first line contains two integers M and N, the number of rows and columns in the factory grid. Both M and N are positive integers not greater than 100.

Each of the next M lines contains N integers separated by spaces. Each integer is 0 or 1. A 0 means the robot can enter that cell, and a 1 means it cannot.

The next line contains the starting row, starting column, and starting direction of the robot. The last line contains the destination row, destination column, and destination direction in the same format.

Directions are encoded as 1 for east, 2 for west, 3 for south, and 4 for north. It is always possible to reach the destination state from the starting state.

Print the minimum number of commands required to move the robot to the destination position while facing the required direction.