Holedox Moving

Holedox is a small snake that lives in a maze. The maze is a grid of $n \times m$ cells; each cell is either a stone or an empty cell, and Holedox may only travel through empty cells. Cells are addressed by (row, column), and the maze exit is the cell (1, 1).

Holedox's body has length $L$ and is described block by block as $B_1(r_1, c_1)\ B_2(r_2, c_2)\ \ldots\ B_L(r_L, c_L)$, where $B_i$ is adjacent to $B_{i+1}$ for every $1 \le i \le L-1$. $B_1$ is the head and $B_L$ is the tail.

To make one move, Holedox chooses a cell adjacent to its head that is empty — that is, the cell is not a stone and is not currently occupied by any block of its body, the tail included. It moves the head into that cell, and at the same time every other block slides into the cell that the block ahead of it just left: $B_2$ into the old cell of $B_1$, $B_3$ into the old cell of $B_2$, and so on up to $B_L$.

For example, suppose the body is $B_1(4,1)\ B_2(4,2)\ B_3(3,2)\ B_4(3,1)$. If the only cell the head can move into is $(5,1)$, then after one move the body becomes $B_1(5,1)\ B_2(4,1)\ B_3(4,2)\ B_4(3,2)$.

Given the maze and the starting position of every block of Holedox's body, compute the minimum number of moves the head needs to reach the exit (1, 1).

The input contains several test cases.

Each test case begins with a line of three integers $n$, $m$ ($1 \le n, m \le 20$) and $L$ ($2 \le L \le 8$): the number of rows, the number of columns, and the length of Holedox's body. The next $L$ lines each contain a row and a column, giving the starting positions of $B_1(r_1,c_1)$ through $B_L(r_L,c_L)$ in order, with $1 \le r_i \le n$ and $1 \le c_i \le m$. The next line contains an integer $K$, the number of stones, and the following $K$ lines each contain the row and column of one stone.

Consecutive test cases are separated by a blank line. The input ends with a line containing three zeros.

It is guaranteed that $B_i$ is adjacent to $B_{i+1}$ for $1 \le i \le L-1$, and that the exit cell (1, 1) is never a stone.

For each test case, print a single line Case X: S, where $X$ is the test-case number (starting from 1) and $S$ is the minimum number of moves the head needs to reach the exit. Print -1 for $S$ if the head can never reach the exit.

In the first example one optimal route for the head is $(4,1) \to (5,1) \to (5,2) \to (5,3) \to (4,3) \to (4,2) \to (4,1) \to (3,1) \to (2,1) \to (1,1)$, which takes 9 moves. Note that the head cannot begin by stepping to $(3,1)$: even though the tail is about to leave that cell, it is still occupied at the moment of the move.