Bloqueos en Cuadradónia

Cuadradónia es una ciudad bien organizada. Recibe su nombre debido a la forma cuadrada que tiene vista desde el aire, y debido a su cuadrado sistema de calles. Entre sus habitantes, hay quienes ya se cansaron de que todo esté tan rectilíneo, y son estas mismas personas las que han comenzado a bloquear las esquinas de las calles, “por un futuro más redondo”.

El sistema de calles presente en Cuadradónia es único. Existen exactamente N calles horizontales y N calles verticales que al intersectarse entre sí resultan en (N * N) esquinas. Toda calle horizontal pasa por las demás calles verticales, y toda calle vertical por las demás calles horizontales. En la ciudad, cada calle recibe un número especial que la identifica:

• Las calles horizontales han sido numeradas desde 0 hasta N - 1, de arriba hacia abajo.
• Las calles verticales han sido numeradas desde 0 hasta N - 1, de derecha a izquierda.

Para referirse a una esquina, la gente menciona primero el número de la calle horizontal y luego el número de la calle vertical. Por ejemplo, el cruce de la horizontal 5 con la vertical 8 se escribiría simplemente (5, 8).

Debido a los bloqueos, desplazarse por la ciudad ya no es tan simple, y el presidente de la Organización de Ciudadanos Ejemplares, Prudentes y Bondadosos (OCEPB) lo sabe. Él debe trasladarse desde su casa en la esquina (Xo,Y o) hasta la sede de la OCEPB en la esquina (Xf,Y f), donde se reunirá con un representante de la Organización de Buenos Individuos (OBI).

Ayuda al presidente de la OCEPB a saber si existe algún camino para llegar a su destino, conociendo el mapa actual de la ciudad y sus bloqueos.

Entrada

La entrada consiste de varios casos de prueba, donde cada caso de prueba tiene varias líneas. A continuación se describe el formato de cada caso:

• En la primera línea se encuentra un único entero N (1 = N = 20) que indica el número de calles verticales y horizontales.
• En la segunda línea se encuentran cuatros enteros Xo, Y o, Xf, Y f que denotan la esquina de origen (Xo,Y o) y la esquina de destino (Xf,Y f). Se garantiza que las esquinas dadas son válidas y que la esquina de origen no es la misma que la de destino.
• A continuación siguen N líneas con N caracteres cada una, indicando la presencia/ausencia de bloqueos en cada esquina de la ciudad. Un carácter B indica que la esquina está bloqueada y un carácter L que una esquina está libre.

La entrada termina cuando N es 0. Este caso no debe ser procesado.

Salida

Por cada caso de prueba: En caso de que exista una ruta sin bloqueos desde el origen al destino, debes imprimir HAY RUTA POSIBLE. Si fuese imposible llegar o si la esquina de destino/origen está bloqueada, imprime NO HAY RUTA POSIBLE.

Ejemplo de Entrada

5  
0 1 1 4  
BLBLB  
LLLLL  
BBBLL  
LBLBB  
BBLLB  
0

Ejemplo de Salida

HAY RUTA POSIBLE