Ejercicio publicado en la regional ACM-ICPC 2006.
La rana vive en un pantano en forma de rejilla de forma rectangular, compuesta de celdas de igual tamaño, algunas de las cuales que son secas, y algunas que son lugares con agua. La Rana vive en una celda seca y puede saltar de una celda seca a otra celda seca en sus paseos por el pantano.

La rana desea visitar a su enamorado que vive en una celda seca en el mismo pantano. Sin embargo la rana es un poco floja y desea gastar el mínimo de energía en sus saltos rumbo a la casa de su cortejo. La Rana conoce cuanta energía gasta en cada uno de sus saltos.

Para cada salto, la rana siempre utiliza la siguiente figura para determinar cuales son los posibles destinos desde la celta donde esta (la celda marca con {\bf F}), y la correspondiente energía en calorías gastada en en el salto.

Ninguna otra celda es alcanzable desde la posición corriente de la rana con un solo salto.

 7  6  5  6  7
 6  3  2  3  6
 5  2   F 2  5
 6  3   2  3  6
 7  6   5  6  7

Su tarea es la de determinar la cantidad de energía mínima que la rana debe gastar para llegar de su casa a la casa de su enamorado.

La entrada contiene varios casos de prueba. La primera linea de un caso de prueba contiene dos enteros, $C$ y $R$, indicando el numero de columnas y filas del pantano ($1 \le C, R \le 1000$).
La segunda linea de los casos de prueba contiene cuatro enteros  $C_f$, $R_f$, $C_t$, y
$R_t$, donde $(R_f, C_f)$ especifican la posición de la casa de la rana y $(
R_t, C_t)$ especifican la casa de enamorada donde ($1 \le C_f, C_t \le C$ y $1
\le R_f, R_t \le R$).
La tercera linea de los casos de prueba contiene un numero entero  $W$ ($0 \le W \le 1000$) indicando los lugares donde hay agua en el pantano. Cada una de las siguientes $W$ lineas contienen cuatro enteros
$C_1$, $R_1$, $C_2$, y $R_2$ ($1 \le C_1 \le C_2 \le C$ y $1 \le
R_1 \le R_2 \le R$) describiendo un lugar acuoso rectangular que abarca coordenadas de las celdas cuyas coordenadas $(x,y)$ son tales que $C_1 \le x \le C_2$ y
$R_1 \le y \le R_2$.  El final de los datos se especifica con $C = R = 0$.

Para cada caso de prueba en la entrada, su programa debe producir una linea de salida, conteniendo el mínimo de calorías consumidas por la rana para llegar desde su casa a la casa de su enamorada.

Si no existe un camino su programa debe imprimir {\tt impossible}.