1944 年，特種兵麥克接到國(guó)防部的命令，要求立即趕赴太平洋上的一個(gè)孤島，營(yíng)救被敵軍俘虜?shù)拇蟊鸲?。瑞恩被關(guān)押在一個(gè)迷宮里，迷宮地形復(fù)雜，但幸好麥克得到了迷宮的地形圖。迷宮的外形是一個(gè)長(zhǎng)方形，其南北方向被劃分為 n 行，東西方向被劃分為 m 列， 于是整個(gè)迷宮被劃分為 n×m 個(gè)單元。每一個(gè)單元的位置可用一個(gè)有序數(shù)對(duì) (單元的行號(hào), 單元的列號(hào)) 來(lái)表示。南北或東西方向相鄰的 2 個(gè)單元之間可能互通，也可能有一扇鎖著的門(mén)，或者是一堵不可逾越的墻。迷宮中有一些單元存放著鑰匙，并且所有的門(mén)被分成 p 類(lèi)， 打開(kāi)同一類(lèi)的門(mén)的鑰匙相同，不同類(lèi)門(mén)的鑰匙不同。

大兵瑞恩被關(guān)押在迷宮的東南角，即 (n,m) 單元里，并已經(jīng)昏迷。迷宮只有一個(gè)入口， 在西北角。也就是說(shuō)，麥克可以直接進(jìn)入 (1,1) 單元。另外，麥克從一個(gè)單元移動(dòng)到另一個(gè)相鄰單元的時(shí)間為 1，拿取所在單元的鑰匙的時(shí)間以及用鑰匙開(kāi)門(mén)的時(shí)間可忽略不計(jì)。

試設(shè)計(jì)一個(gè)算法，幫助麥克以最快的方式到達(dá)瑞恩所在單元，營(yíng)救大兵瑞恩。

第一行有三個(gè)整數(shù),分別表示 n,m,p的值。

第二行是一個(gè)整數(shù)k，表示迷宮中門(mén)和墻的總數(shù)。

第 i+2 行 (1≤i≤k)，有 5 個(gè)整數(shù)，依次為 x_i1,y_i1,x_i2,y_i2,g_i:當(dāng) g_i≥1 時(shí)，表示 (x_i1,y_i1)單元與 (x_i2,y_i2) 單元之間有一扇第 g_i 類(lèi)的門(mén)，當(dāng) g_i=0時(shí)， 表示 (x_i1,y_i1) 單元與 (x_i2,y_i2) 單元之間有一堵不可逾越的墻。

第 k+3行是一個(gè)整數(shù) s，表示迷宮中存放的鑰匙總數(shù)。

第 k+3+j行 (1≤j≤s) ，有 3 個(gè)整數(shù)，依次為 x_i1,y_i1,q_i，表示第 j 把鑰匙存放在 (x_i1,y_i1) 單元里，并且第 j 把鑰匙是用來(lái)開(kāi)啟第 q_i 類(lèi)門(mén)。

輸入數(shù)據(jù)中同一行各相鄰整數(shù)之間用一個(gè)空格分隔。

4 4 9
9
1 2 1 3 2
1 2 2 2 0
2 1 2 2 0
2 1 3 1 0 
2 3 3 3 0
2 4 3 4 1
3 2 3 3 0
3 3 4 3 0
4 3 4 4 0
2
2 1 2 
4 2 1

14