Asteroids!

No attempts yetTime limit1sMemory limit128 MB

Problem

You're in space.
You want to get home.
There are asteroids.
You don't want to hit them.

Input

The input holds at least one and at most 100 data sets. Each data set follows the format below, and no blank lines separate them.

A data set has five parts.

  1. Start line. One line, START N, with 1N101 \le N \le 10.
  2. Slice list. NN slices in order. Each slice is an N×NN \times N matrix cut horizontally through the asteroid field, one matrix row per line, so N×NN \times N lines in total. Every position holds one of two values.
    • O (the letter oh) empty space
    • X (upper case) an asteroid
  3. Starting position. One line, A B C, the coordinates A,B,C\langle A, B, C \rangle your craft starts from. The three values are integers separated by single spaces.
  4. Target position. One line, D E F, the coordinates D,E,F\langle D, E, F \rangle you have to reach. The three values are integers separated by single spaces.
  5. End line. One line, END. The last data set may leave this line out.

The origin of the coordinate system is 0,0,0\langle 0, 0, 0 \rangle, so every component of every coordinate is an integer between 00 and N1N-1, inclusive.

  • The first value is the column. The left column is 00.
  • The second value is the row. The top row is 00.
  • The third value is the slice. The first slice is 00.

Both the starting position and the target position are empty space.

Output

Print one line for each data set, with no blank lines between the lines.

If a route exists, print two integers separated by a space. The first is the NN of that data set, the second is the least number of moves needed to get from the starting position to the target position. If no route exists, print NO ROUTE instead.

A move goes in one of the six basic directions: up, down, left, right, forward, back. Put precisely, a move increments or decrements a single component of your current position vector by 11. You cannot move into a cell that holds an asteroid, and you cannot leave the field.