题目背景

W最近沉迷于“摸金”游戏，“八宝粥行动”，在局内搜索物资并且要在规定时间范围内撤离。

题目描述

他选择了一个 $N×M$ 的方格迷宫作为这次探索的地图。默认情况下，所有相邻的格子都是连通的。W的初始位置在左上角即 $(1,1)$ 处，撤离点位于 右下角 即 $(N,M)$。 W只能在上下左右四个方向进行行动，每次移动耗时为 $1$。 在地图中，部分相邻的格子之间可能存在门或墙。

墙：一堵无法逾越的障碍。

门：一扇需要用 房卡 打开的门。门可以双向通过，但需要对应类型的房卡。

所有门被分为 $P$ 类，打开同一类的门的房卡相同，不同类门的房卡不同。 地图中存放着很多房卡，一个格子可能放有多张房卡。当W到达一个有房卡的格子时，就会立即获得这些房卡，此过程不消耗时间。使用房卡开门的时间也可以忽略不计。 现在剩余撤离时间不多，W想让你帮他设计一个算法能最快到达撤离点。

输入

第一行三个整数分别表示 $N，M，P$ 的值。

第二行是一个整数 $k$ 表示地图中门和墙的总数。

接下来 $k$ 行，每行五个整数 $X1, Y1, X2, Y2, G$： 当 $G = 0$ 时，表示$(X1,Y1)$ 与 $(X2,Y2)$ 之间有一面不可逾越的墙。 当 G ≥ 1 时，表示 $(X1,Y1)$ 与 $(X2,Y2)$ 之间有一扇类型为 G 的门。

接下来一行，包含一个整数 $S$ 表示地图中存在的房卡的数量。

接下来 $S$ 行，每行三个整数 $X, Y, Q$ 表示在 $(X, Y)$ 这个点上有一张类型为$Q$的房卡。

输出

输出W最短的撤离时间。 如果无法撤离，则输出 $-1$。

样例

输入数据1

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

输出数据1

14

数据范围

对于所有测试数据，保证输入中描述的 $(X1, Y1)$ 与 $(X2, Y2)$ 两点相邻，即 $|X1−X2|+|Y1−Y2|=1$

$1≤N,M,P≤10$

$1≤P≤10$

$0≤Gi≤P$

$1≤Qi≤P$

$1≤S≤60$

$1≤k≤120$