Giải bài trực tuyến

Hôm nay là ngày hội Halloween, Gà Tơ và các bạn của cậu ta quyết định tổ chức một trò chơi để mừng ngày hội này : Đi qua khu nghĩa địa. Lần lượt từng người sẽ thử sức băng qua một khu nghĩa địa ở một khu rừng, và bây giờ đến lượt của Tơ. Gà Tơ vẫn còn nhớ khi nhỏ, bà cậu từng kể, vào các đêm Halloween, ở các khu nghĩa địa sẽ xuất hiện các "Lỗ đen". Đó không phải là các lỗ bình thường. Khi một ai đó bị rơi vào trong hố, nó sẽ đưa người đó đến một nơi bất kì trong nghĩa địa, có thể rất xa. Tuy nhiên, điều đáng sợ hơn nữa là nó có thể "dịch chuyển thời gian". Tức là, nếu bạn bị rơi vào trong "Hố đen", bạn sẽ bị đưa đến một nơi nào đó trong nghĩa địa, tại một thời điểm nào đó (có thể trước hoặc sau khi bạn bị rơi vào hố).

Nghĩa địa được mô tả như một lưới có kích thước W x H, lối vào bắt đầu từ ô (0,0) và kết thúc ở ô (W-1,H-1). Vì sợ bóng tối và sợ bị bọn ma đói ăn thịt, Gà Tơ quyết định đi ra khỏi nghĩa địa càng sớm càng tốt, ngay khi nó đến được lối ra, và sẽ không bao giờ đặt chân trở lại bất cứ đâu trong nghĩa địa nữa. Từ 1 ô, Tơ có thể đi sang 4 ô kề cạnh. Mỗi ô có thể là một bia đá, một "Hố đen" hoặc là đám cỏ:

• Nếu ô là một bia mộ, Tơ sẽ không thể đi qua được nó vì nó quá cao, mà cậu lại chưa biết bay.
• Nếu ô là một "Hố đen" và Tơ đi vào nó, nó sẽ đưa cậu ta đến một vị trí nào đó ở nghĩa địa với một độ chênh lệch thời gian. Mỗi "Hố đen" có thể có độ chênh lệch thời gian khác nhau và có thể = 0.
• Ngược lại, nếu ô là cỏ thì Tơ có thể đi qua bình thường.

Gà Tơ rất lo lắng vì sợ bị làm mồi cho bọn ma đói, nên đã thông báo cho các vCoders. Hãy viết một chương trình giúp bạn Gà Tơ của chúng ta tính chính xác thời gian nhỏ nhất để có thể thoát khỏi nghĩa địa. Gà Tơ chấp nhận đi vào trong "Hố đen" nếu điều đó giúp cậu ta có thể thoát ra khỏi nghĩa địa sớm hơn. Tuy nhiên, "Hố đen" có thể khiến cho Gà Tơ không thể tìm được một đường đi để thoát ra khỏi nghĩa địa với thời gian nhỏ nhất có thể xác định được, chương trình của bạn phải đưa ra thông báo trong trường hợp này.

Hình trên mô tả một nghĩa địa có 2 bia mộ ở (2;1) và (3;1), một "Hố đen", dịch chuyển từ (3;0) đến (2;2) với chênh lệch thời gian là 0s

(0;0) -> (1;0) -> (2;0) -> (3;0 )------------------------- (2;2) -> (3;2)

        1s    +    1s    +    1s    +        [HỐ ĐEN - 0s]            +   1s                = 4s

Nếu không sử dụng "Hố đen", Gà Tơ phải mất 5s để có thể thoát ra khỏi nghĩa địa.

Input

Nhiều test, mỗi test bắt đầu bằng một dòng chứa 2 số nguyên W và H (1<= W,H <= 30) là chiều rộng và cao của nghĩa địa.

Dòng sau chứa 1 số nguyên G (G>=0) - Số bia trong nghĩa địa, theo sau là G dòng, mỗi dòng chứa vị trí bia là 2 số nguyên X và Y (0<=X

Dòng tiếp theo chứa 1 số nguyên E (E >=0) là số "Hố đen", theo sau là E dòng, mỗi dòng chứa 5 số nguyên X1,Y1,X2,Y2,T với (X1;Y1) là vị trí của "Hố đen" và (X2;Y2) là nơi chuyển đến với chênh lệch thời gian là T (-10000 <= T <= 10000).

Không có 2 "Hố đen" nào ở cùng 1 vị trí, tại điểm có "Hố đen" không có một bia mộ nào.

Không có bia mộ cũng như "Hố đen" nào tại (0;0) và (W-1;H-1).

Kết thúc test là dòng chứa 0 0.

Output

Mỗi test, nếu Gà Tơ có thể di chuyển vô hạn định về quá khứ , đưa ra Never.

Còn không

Nếu có thể đi ra khỏi nghĩa địa, đưa ra thời gian nhỏ nhất.

Nếu không thể ra khỏi nghĩa địa, đưa ra Impossible.

Example

Input:
4 3

2

2 1

3 1

1

3 0 2 2 0

4 2

0

1

2 0 1 0 -3

3 3

2

2 1

1 2

0

0 0

Output:
4

Never

Impossible