Background

$\texttt{WSM}$ is an adventure game, and WSM is the main character of this game.

Problem Description

There is a map made of a grid with $n$ rows and $m$ columns. WSM starts from the top-left cell with coordinates $(1,1)$ and needs to reach the cell with coordinates $(a,b)$.

There are $k$ password locks and $t$ password keys on the map.
When WSM arrives at the cell containing a key with password $r$, the lock with password $r$ disappears immediately.
At any moment, WSM must stay within the map, and the cell WSM is in must not have a lock.
If a cell contains both a lock with password $r$ and a key with password $r$, then WSM can enter that cell.

There are also $p$ normal items and $q$ magic items on the map. WSM can spend steps to use normal items and magic items on the map. All items and magic items can be reused.

Normal items are very primitive: WSM can only use an item that is in the same cell as WSM.
Suppose WSM is currently at $(x,y)$. After using an item, WSM moves to $(x',y')$.

Magic items are fragile: when WSM is in the same cell as some magic item, that magic item will disappear permanently.
Magic items are powerful: WSM can use any magic item on the map.
Suppose WSM is currently at $(x,y)$, and the magic item is at $(x_0,y_0)$. After using the magic item, WSM moves to $(x',y')$.

In each step, WSM can use one normal item or one magic item. What is the minimum number of steps needed to move from the cell $(1,1)$ to the cell $(a,b)$?

Input Format

The first line contains four integers $n,m,a,b$.
The second line contains four integers $k,t,p,q$.
The next $k$ lines each contain three integers $x,y,r$, meaning there is a lock with password $r$ at cell $(x,y)$.
The next $t$ lines each contain three integers $x,y,r$, meaning there is a key with password $r$ at cell $(x,y)$.
The next $p$ lines each contain three integers $x,y,id$, meaning there is a normal item with ID $id$ at cell $(x,y)$.
The next $q$ lines each contain three integers $x,y,id$, meaning there is a magic item with ID $id$ at cell $(x,y)$.

Output Format

Output one integer, the minimum number of steps WSM needs. If it is impossible to reach, output -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

Hint

Sample $1$ Explanation

The route with the minimum number of steps is:

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

Constraints

This problem uses bundled testdata.

Note: In any cell, there may simultaneously exist multiple locks, keys, items, and magic items.

For all testdata, it is guaranteed that:

• $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$。
• For all locks, keys, items, and magic items, $1\le x\le n$，$1\le y\le m$。
• For all locks, $1\le r\le 10^9$。
• For all keys, $1\le r\le 10^9$。
• For all normal items, $id\in\{1,2,3,4\}$。
• For all magic items, $id\in\{1,2,3\}$。

Translated by ChatGPT 5