Lazy Jumping Frog

Mr. Frog lives in a rectangular marsh made up of equally sized square cells; each cell is either dry land or a watery place.

Mr. Frog lives on a dry cell and, as he wanders, can jump only from a dry cell to another dry cell. He wants to visit his girlfriend, Ms. Toad, who also lives on a dry cell in the same marsh. But Mr. Frog is lazy and wants to spend as little energy as possible on his way to Ms. Toad's home.

For any single jump, the cells Mr. Frog can reach and the energy (in calories) he spends are given by the figure below. In the figure, F is Mr. Frog's current cell, and the number written in a cell is the calories spent to jump there in one move. Any cell not shown in the figure cannot be reached in a single jump.

In other words, from his current cell he may jump to any cell whose column offset and row offset are both at most $2$ (excluding the cell itself), and the calories spent are:

• one cell up, down, left, or right (straight distance $1$): $2$ calories
• one cell diagonally ($1$ in each of column and row): $3$ calories
• two cells straight in one direction (horizontally or vertically by $2$): $5$ calories
• $2$ cells in one direction and $1$ in the other (a knight-like move): $6$ calories
• $2$ cells in each of column and row (a far diagonal): $7$ calories

The target cell of every jump must also be dry. Determine the minimum energy Mr. Frog needs to spend to get from his home to Ms. Toad's home.

The input consists of several test cases.

The first line of a test case contains two integers $C$ and $R$, the number of columns and rows of the marsh ($1 \le C, R \le 1000$). The second line contains four integers $C_f, R_f, C_t, R_t$, where $(C_f, R_f)$ is Mr. Frog's home and $(C_t, R_t)$ is Ms. Toad's home ($1 \le C_f, C_t \le C$ and $1 \le R_f, R_t \le R$). The third line contains an integer $W$, the number of watery places ($0 \le W \le 1000$). Each of the next $W$ lines contains four integers $C_1, R_1, C_2, R_2$ ($1 \le C_1 \le C_2 \le C$ and $1 \le R_1 \le R_2 \le R$), describing a rectangular watery place consisting of all cells whose coordinates $(x, y)$ satisfy $C_1 \le x \le C_2$ and $R_1 \le y \le R_2$.

The end of input is indicated by $C = R = 0$.

For each test case, print on one line the minimum calories Mr. Frog spends to travel from his home to Ms. Toad's home. If there is no way to reach Ms. Toad's home, print impossible.