게으른 점프 개구리

개구리 군은 직사각형 모양의 습지에 산다. 습지는 크기가 같은 정사각형 칸들로 이루어져 있으며, 각 칸은 마른 땅이거나 물웅덩이다.

개구리 군은 마른 칸에 살며, 이동할 때 마른 칸에서 다른 마른 칸으로만 뛸 수 있다. 그는 같은 습지의 마른 칸에 사는 여자친구 두꺼비 양의 집에 가려고 한다. 하지만 개구리 군은 게을러서, 두꺼비 양의 집에 도착할 때까지 소모하는 에너지를 최소화하고 싶다.

한 번 뛸 때 개구리 군이 갈 수 있는 칸과 그때 소모하는 에너지(칼로리)는 아래 그림으로 정해진다. 그림에서 F는 개구리 군의 현재 칸이고, 각 칸에 적힌 숫자는 그 칸으로 한 번에 뛸 때 드는 칼로리다. 그림에 나타나지 않은 칸으로는 한 번에 갈 수 없다.

즉, 현재 칸을 기준으로 열 차이와 행 차이가 모두 $2$ 이하인 칸(자기 자신 제외)으로 뛸 수 있으며, 소모하는 칼로리는 다음과 같다.

• 상하좌우로 한 칸(직선 거리 $1$): $2$칼로리
• 대각선으로 한 칸(가로·세로로 각각 $1$): $3$칼로리
• 한 방향으로 두 칸 직선(가로 또는 세로로 $2$): $5$칼로리
• 한 방향으로 $2$칸, 다른 방향으로 $1$칸(나이트 이동): $6$칼로리
• 가로·세로로 각각 $2$칸(먼 대각선): $7$칼로리

목표 칸도 반드시 마른 칸이어야 한다. 개구리 군의 집에서 두꺼비 양의 집까지 가는 데 필요한 최소 에너지를 구하여라.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 습지의 열(column) 수와 행(row) 수를 나타내는 두 정수 $C$와 $R$가 주어진다 ($1 \le C, R \le 1000$). 둘째 줄에는 네 정수 $C_f, R_f, C_t, R_t$가 주어지며, $(C_f, R_f)$는 개구리 군의 집 위치, $(C_t, R_t)$는 두꺼비 양의 집 위치다 ($1 \le C_f, C_t \le C$, $1 \le R_f, R_t \le R$). 셋째 줄에는 물웅덩이의 개수를 나타내는 정수 $W$가 주어진다 ($0 \le W \le 1000$). 이어지는 $W$개의 각 줄에는 네 정수 $C_1, R_1, C_2, R_2$가 주어지며 ($1 \le C_1 \le C_2 \le C$, $1 \le R_1 \le R_2 \le R$), 이는 좌표 $(x, y)$가 $C_1 \le x \le C_2$이고 $R_1 \le y \le R_2$인 모든 칸으로 이루어진 직사각형 물웅덩이를 뜻한다.

입력의 끝은 $C = R = 0$인 줄로 표시된다.

각 테스트 케이스마다 개구리 군이 집에서 두꺼비 양의 집까지 가는 데 드는 최소 칼로리를 한 줄에 출력한다. 두꺼비 양의 집에 도달할 방법이 없으면 impossible을 출력한다.