题目背景

$\texttt{WSM}$ 是一款冒险游戏，WSM 是这个游戏的主角。

题目描述

有一个由 $n$ 行 $m$ 列格子构成的地图。WSM 要从地图的左上角坐标为 $(1,1)$ 的格子出发，到达坐标为 $(a,b)$ 的格子。

地图上有 $k$ 个带有密码的锁和 $t$ 个带有密码的钥匙。
当 WSM 到达密码为 $r$ 的钥匙所在的格子，密码为 $r$ 的锁就会立刻消失。
任何一个时刻，WSM 都必须在地图内，且所处的格子必须没有锁。
如果某个格子中既有密码为 $r$ 的锁又有密码为 $r$ 的钥匙，那么 WSM 可以进入到这个格子。

地图上还存在着 $p$ 个普通道具和 $q$ 个魔法物品。WSM 可以消耗步数来使用地图上的普通道具和魔法物品。所有的道具和魔法物品均可重复使用。

---

道具很原始，WSM 只能使用和自己在同一格的道具。
假设 WSM 当前位置为 $(x,y)$，使用道具后移动到 $(x',y')$。
|道具编号|移动后位置| |:-:|:-:| $1$|WSM 向上走一格，即 $(x',y')=(x-1,y)$| $2$|WSM 向下走一格，即 $(x',y')=(x+1,y)$| $3$|WSM 向左走一格，即 $(x',y')=(x,y-1)$| $4$|WSM 向右走一格，即 $(x',y')=(x,y+1)$|

---

魔法物品很脆弱，当 WSM 和某一个魔法物品处在同一格时，这个魔法物品会永久消失。
魔法物品很强大，WSM 可以使用地图上任意一个魔法物品。
假设 WSM 当前位置为 $(x,y)$，魔法物品的位置为 $(x_0,y_0)$，使用魔法物品后移动到 $(x',y')$。
|魔法物品编号|移动后位置| |:-:|:-:| $1$|$\frac{x+x'}{2}=x_0$，$\frac{y+y'}{2}=y_0$| $2$|$x'=x$，$\frac{y+y'}{2}=y_0$| $3$|$\frac{x+x'}{2}=x_0$，$y'=y$|

WSM 每一步可以使用一个道具或一个魔法物品。请问至少需要多少步才能从坐标为 $(1,1)$ 的格子到达坐标为 $(a,b)$ 的格子？

输入格式

第一行输入四个整数 $n,m,a,b$。
第二行输入四个整数 $k,t,p,q$。
接下来 $k$ 行，每行输入三个整数 $x,y,r$，表示坐标 $(x,y)$ 的格子上有密码为 $r$ 的锁。
接下来 $t$ 行，每行输入三个整数 $x,y,r$，表示坐标 $(x,y)$ 的格子上有密码为 $r$ 的钥匙。
接下来 $p$ 行，每行输入三个整数 $x,y,id$，表示坐标 $(x,y)$ 的格子上有编号为 $id$ 的道具。
接下来 $q$ 行，每行输入三个整数 $x,y,id$，表示坐标 $(x,y)$ 的格子上有编号为 $id$ 的魔法物品。

输出格式

输出一个整数，表示 WSM 所需的最小步数，如果无法到达则输出 -1。

2 2 2 2
0 0 8 0
1 2 4
1 1 2
2 2 1
1 1 4
2 2 4
2 1 4
1 2 3
2 1 1

2

提示

【样例 $1$ 解释】

花费最小步数的路线为：

$\def\f#1{\xrightarrow{\bf 道具#1}} (1,1) \f{2} (2,1) \f{4} (2,2)$。

【数据范围】

本题采用捆绑测试。

请注意：任意一个格子内可能同时存在多个锁、钥匙、道具和魔法道具。

对于所有测试数据，保证：

• $1\le n,m\le400$，$1\le a\le n$，$1\le b\le m$。
• $1\le k \le 10^3$，$0\le t\le 3$，$1\le p\le 5\times 10^5$，$0\le q\le 3$。
• 对于所有的锁、钥匙、道具、魔法物品，均有 $1\le x\le n$，$1\le y\le m$。
• 对于所有的锁，均有 $1\le r\le 10^9$。
• 对于所有的钥匙，均有 $1\le r\le 10^9$。
• 对于所有的道具，均有 $id\in\{1,2,3,4\}$。
• 对于所有的魔法物品，均有 $id\in\{1,2,3\}$。

子任务编号	$n,m\le$	$k\le$	$t\le$	$p\le$	$q\le$	分数
$1$	$2$	$0$		$13$	$0$	$10$
$2$	$10$	^		$300$	$3$
$3$	^	$100$	$3$	^		$20$
$4$	$400$	$0$		$5\times10^5$	$0$	$10$
$5$	^	$3$		^	$3$	$25$
$6$		$10^3$	^		^