Se dispone de una superficie rectangular "cuadriculada", es decir, formada por un entramado de posiciones o casillas (como ocurre, por ejemplo, con un tablero de ajedrez). Nos interesa buscar caminos dentro de esta superficie que cumplan ciertas condiciones, teniendo en cuenta que algunas de las casillas no pueden formar parte de dichos caminos (para entendernos, representan obstáculos en la superficie).

Objetivo

Dada una superficie rectangular de dimensión n x m, realizar un programa que la recorra partiendo de una casilla inicial y llegando a una casilla final según las reglas siguientes:

• Todas las casillas deberán ser visitadas excepto las casillas marcadas como no visitables.
• No se podrá visitar más de una vez cada casilla.
• El salto de una casilla a otra deberá realizarse siguiendo las reglas de movimiento del caballo de ajedrez. Esto es, desde una casilla sólo se podrá avanzar a aquellas resultantes de avanzar una posición en línea recta y otra en diagonal en la misma dirección. El siguiente esquema muestra las casillas accesibles (con una cruz) desde la casilla A:

El programa deberá calcular la secuencia de casillas visitadas desde la inicial hasta la final. En caso que no exista ninguna solución, el programa debe detectar esta situación e informar.

Entrada

La entrada del programa consiste en una secuencia de líneas, que residen en un archivo de texto (ASCII) con nombre CAB.DAT, que tendrá el siguiente formato:

• La primera línea contiene la dimensión de la superficie, es decir, el número n de columnas y el número m de filas.
• La segunda línea contiene la posición inicial y la posición final, cada posición siendo dos enteros, la columna y la fila respectivamente. Podéis suponer que las dos posiciones están dentro de los límites de la superficie.
• A continuación, m líneas más. Cada línea representa una fila de la superficie, y contiene n caracteres, uno por columna. Cada uno de estos caracteres puede ser 'V' o 'N', dependiendo de si la posición correspondiente es visitable o no. Los caracteres aparecen separados por un único carácter "espacio".

A efectos de numeración, debe considerarse que las filas van de 1 a m y las columnas de 1 a n.

Salida

La salida del programa ha de grabarse en un archivo de texto (ASCII) con nombre CAB.RES, que contendrá una línea por cada posición que forme parte del camino encontrado como solución que cumpla las condiciones dadas en el enunciado. Cada posición es un par de enteros: la columna y la fila. La primera posición de la solución será la posición inicial, y la última la posición final.

Si no hay ninguna solución, el fichero CAB.RES contendrá una única línea con el texto INSATISFACTIBLE. Si existe más de una solución, cualquiera de ellas se considera válida.

Ejemplo de entrada

5 4
1 1
1 4
V V V N N
V N V V V
V V V N V
V V V V V

Ejemplo de salida

1 1
2 3
4 4
5 2
3 1
1 2
2 4
3 2
5 3
3 4
1 3
2 1
4 2
5 4
3 3
1 4