P13563 "WWOI R1" WSM Game

[$\texttt{WSM}$](https://gitblock.cn/Projects/769996) is an adventure game, and WSM is the main character of this game.

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')$. |Item ID|Position after moving| |:-:|:-:| $1$|WSM moves up by one cell, i.e. $(x',y')=(x-1,y)$| $2$|WSM moves down by one cell, i.e. $(x',y')=(x+1,y)$| $3$|WSM moves left by one cell, i.e. $(x',y')=(x,y-1)$| $4$|WSM moves right by one cell, i.e. $(x',y')=(x,y+1)$| --- 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')$. |Magic item ID|Position after moving| |:-:|:-:| $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$| 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)$?

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

### 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\}$。 | Subtask ID |$n,m\le$|$k\le$|$t\le$|$p\le$|$q\le$|Score| |:-:|:-:|:-:|:-:|:-:|:-:|:-:| |$1$|$2$|$0$|$0$|$13$|$0$|$10$| |$2$|$10$|^|^|$300$|$3$|$10$| |$3$|^|$100$|$3$|^|^|$20$| |$4$|$400$|$0$|$0$|$5\times10^5$|$0$|$10$| |$5$|^|$3$|$3$|^|$3$|$25$| |$6$|^|$10^3$|^|^|^|$25$| Translated by ChatGPT 5