Direct Visibility

Building and operating a mobile phone network is expensive and complex. After the base transceiver stations (BTS) are built and working, technicians must take many measurements to determine the state of the network and to plan effective improvements.

A technician carries special equipment that measures field strength, transmitter power, and signal quality. The equipment sits in a large backpack, and the technician walks with it from one BTS to another. The backpack has only a small cache that holds the measured values for a few seconds; the values must then be sent to a BTS over an infrared (IrDA) link. The infrared link works only when there is direct visibility between the technician and the BTS.

Your task is to find a walking path between two neighbouring BTSes such that, at the end of every step, at least one of the two BTSes is visible.

The first line contains a single positive integer T, the number of test cases that follow. Each test case describes a town.

A town is a rectangular grid of P by Q square fields, each field 1 metre wide. For every field (i, j) a non-negative integer Z(i, j) gives the terrain height in metres. The town is therefore made of unit cubes; every cube is either solid or empty, and there are no "half solid" cubes. A field of height h means the cubes at levels 0 through h-1 are solid and every cube above is empty.

The first line of each test case contains two integers P and Q, separated by one space (1 ≤ P, Q ≤ 200). The next P lines each contain Q integers separated by spaces; these are the heights Z(i, j), with 1 ≤ i ≤ P, 1 ≤ j ≤ Q and 0 ≤ Z(i, j) ≤ 5000. The last line of each test case contains four integers R1, C1, R2, C2 (1 ≤ R1, R2 ≤ P, 1 ≤ C1, C2 ≤ Q), the positions of the two BTSes. The first coordinate R is the row, the second coordinate C is the column.

The technician moves one step at a time between two neighbouring fields, in one of the four directions North, South, West, or East; diagonal moves are not allowed. A step from field A to field B is allowed only if the height difference is small: in a single step the technician may climb at most 1 metre up or descend at most 3 metres down.

At the end of every step, at least one of the two BTSes must be visible (in the middle of a step visibility may be lost, and the cache handles that). Model both the BTS and the technician as points exactly half a metre above the surface, in the centre of their fields — that is, the centre of the unit cube that sits directly above the terrain at that position. One BTS is visible from the technician when the straight line joining these two points does not pass through the interior of any solid cube. The line may touch solid cubes: an infrared beam can pass between two cubes that meet only along an edge, because it touches both cubes without entering the interior of either.

Find the shortest path that satisfies all of the above rules: every step is between neighbouring fields, no step climbs or descends too much, and after every step at least one BTS is visible.

For each test case print one line. If a valid path exists, print The shortest path is M steps long., where M is the smallest possible number of steps. If no such path exists, print Mission impossible!.