할로윈 묘지

오늘은 할로윈이다. 상근이와 친구들은 할로윈을 기념하기 위해 묘지를 찾았다. 이들은 한 명씩 묘지로 들어가 혼자서 묘지의 출구를 찾아야 한다. 이제 상근이의 차례가 되었다.

상근이가 어렸을 때, 할머니는 상근이에게 할로윈 밤이면 묘지에 귀신 구멍이 나타난다고 말해 주었다. 귀신 구멍으로 들어가면 묘지의 다른 곳으로 다시 나오게 된다. 이 구멍은 시간을 이동시키는 구멍이다. 귀신 구멍에 떨어지면, 특정 시간이 지난 뒤(또는 그 전에) 평행 우주의 다른 구멍에서 나오게 된다.

묘지는 W × H 크기의 격자로 나타낼 수 있다. 묘지의 입구는 (0, 0)이고 출구는 (W-1, H-1)이다. 상근이는 겁이 많아서 최대한 빨리 묘지를 빠져나가려고 하며, 이동하던 도중 출구에 도달하면 뒤도 돌아보지 않고 그 즉시 묘지를 빠져나간다. 상근이는 현재 칸에서 동, 서, 남, 북으로 인접한 칸으로 이동할 수 있고, 한 번 이동하는 데 1초가 걸린다. 각 칸은 잔디, 묘비, 또는 귀신 구멍이다.

• 묘비는 매우 높기 때문에, 묘비가 있는 칸으로는 이동할 수 없다.
• 귀신 구멍이 있는 칸으로 이동하면, 특정 시간이 지난 뒤 묘지의 다른 곳에서 상근이가 나타난다. 이 시간은 귀신 구멍마다 다르며, 양수, 음수, 0 중 하나이다.
• 잔디가 있는 칸으로는 자유롭게 이동할 수 있다.

상근이는 묘지를 빨리 빠져나가기 위해 귀신 구멍도 이용한다. 묘지를 빠져나갈 수 없는 경우나, 계속해서 과거로 이동하게 되는 경우도 있을 수 있다.

예를 들어, 4 × 3 크기의 묘지에서 묘비가 (2, 1)과 (3, 1)에 있고, (3, 0)으로 들어가면 0초 만에 (2, 2)에서 나오는 귀신 구멍이 하나 있다고 하자. 이때 묘지를 빠져나오는 가장 빠른 시간은 4초이며, 경로는 다음과 같다.

(0, 0) → 동(1초) → (1, 0) → 동(1초) → (2, 0) → 동(1초) → (3, 0) → 귀신 구멍(0초) → (2, 2) → 동(1초) → (3, 2)

귀신 구멍을 이용하지 않으면 가장 빠른 시간은 5초이다.

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

각 테스트 케이스의 첫째 줄에는 묘지의 너비 W와 높이 H가 주어진다 ($1 \le W, H \le 30$). 다음 줄에는 묘비의 개수 G가 주어진다 ($G \ge 0$). 다음 G개 줄에는 묘비의 위치를 나타내는 두 정수 X와 Y가 주어진다 ($0 \le X < W$, $0 \le Y < H$).

다음 줄에는 귀신 구멍의 수 E가 주어진다 ($E \ge 0$). 다음 E개 줄에는 귀신 구멍의 정보를 나타내는 다섯 정수 X1, Y1, X2, Y2, T가 주어진다. (X1, Y1)은 귀신 구멍의 위치이고, (X2, Y2)는 그 구멍으로 들어갔을 때 나오는 위치이다 ($0 \le X1, X2 < W$, $0 \le Y1, Y2 < H$). (X1, Y1)과 (X2, Y2)는 같을 수도 있다. T는 귀신 구멍에서 나오는 데 걸리는 시간이며 ($-10,000 \le T \le 10,000$), T가 양수이면 귀신 구멍에 들어간 뒤에 나온다는 뜻이다. 두 귀신 구멍이 같은 곳에 있거나, 구멍에서 나오는 지점이 묘비인 경우는 없다. 묘비나 귀신 구멍이 (0, 0)이나 (W-1, H-1)에 있는 경우도 없다.

입력의 마지막 줄에는 0 0이 주어진다.

각 테스트 케이스마다, 상근이가 계속해서 과거로 돌아가게 되면 Never를 출력하고, 출구로 빠져나올 수 없으면 Impossible을 출력한다. 그 외의 경우에는 묘지를 빠져나오는 가장 빠른 시간(초)을 출력한다.