测试数据来自 system/1879

描述

在一个给定的迷宫中（由空白格子与障碍物构成），小岛养了一只贪吃蛇。
这只贪吃蛇的身长为L，我们可以用迷宫中连续的（这里的连续指有公共边的两个格子）L个格子来描述：
(X1,Y1) (X2,Y2) ... (XL,YL)
其中 (X1,Y1) 是贪吃蛇的头。
现在，小岛给出了这只贪吃蛇的起始位置状态，并希望求得一种移动方案使得可以引导贪吃蛇在满足移动原则的情况下用最少的步数到达出口（1，1）。
移动原则为，当与头相邻的一个格子不是障碍物也不是自己身体的一个部分时，即可将头移动至该格并将身体的各个部分依次向前移动1格。(特别注意: 如果蛇头与蛇尾相邻, 也不允许下一步将头移动到尾现在所处的位置, 虽然按照移动规则, 头移动过去的一瞬间,尾巴就会离开那一个格子.)

格式

输入格式

每一个测试点由多组数据组成（最多3组）。
每一组数据的第一行有三个整数 n, m 和 L，表示迷宫的行数与列数（行与列均从1开始标号），还有贪吃蛇的长度。
之后 L 行，每一行给出一对整数 (x,y) 表示贪吃蛇身体每一部分的坐标。依次为 (X1,Y1) 到 (XL,YL)。
之后一行给定整数 K，表示迷宫中障碍的个数。
之后 K 行，每行给出一对整数依次表示每一个障碍物所在的位置。
每两组数据之间有一处空行。
输入数据的最后一行为三个零表示结束。

我们保证贪吃蛇身体的初始情况总是依次连接着的。

输出格式

对于每一组数据，输出一行：包括测试数据的编号与贪吃蛇最少需要移动的步数，如果无解，则输出-1。

样例1

样例输入1

5 6 4
4 1
4 2
3 2
3 1
3
2 3
3 3
3 4

4 4 4
2 3
1 3
1 4
2 4
4
2 1
2 2
3 4
4 2

0 0 0

样例输出1

Case 1: 9
Case 2: -1

限制

对于10%的数据: n, m <= 5
对于50%的数据: n, m <= 10
对于100%的数据: n, m <= 20, 2 <= L <= 8

每一个测试点的时间限制为2秒.

提示

我们用 '.' '#' 和数字 1 ~ L 表示空地, 障碍物 和蛇的身体(1是头), 那么初始状态为:

......
..#...
43##..
12....
......

最优方案是, 先向下再向右, 移动到下图的位置:

......
..#...
..##..
34....
21....

然后向右再向上, 移动到下图的位置:

......
..#...
..##..
..1...
432...

之后再 "左 上 上 上 左" 扭动到 (1,1)的位置就可以了, 总计步数为9.