Rescue Mission: Maze Escape

In 1944, special forces soldier Mike receives an urgent order from the Department of Defense to rescue soldier Ryan, who has been captured and is held in a maze on a remote Pacific island. The maze is a rectangular grid of size (N \times M) (with (N) rows and (M) columns). Each cell in the maze is denoted by its coordinates ((i,j)). Adjacent cells (either north-south or east-west) may be connected by an open passage, separated by a locked door, or divided by an impassable wall. There are (P) types of locked doors, and a key corresponding to each type can open all doors of that type. Some cells contain a key and picking up a key or unlocking a door takes no extra time. Mike enters the maze at the top-left cell ((1,1)) and must reach the bottom-right cell ((N,M)) as quickly as possible. Moving between two adjacent cells takes 1 unit of time. If it is impossible to reach the destination, print (-1).

inputFormat

The input has the following format:\ (N) (M) (P)\ (K)\ Next (K) lines: each line contains three integers (r), (c), and (t), indicating that cell ((r, c)) contains a key that opens doors of type (t).\ (E)\ Next (E) lines: each line contains five integers (r_1) (c_1) (r_2) (c_2) (d), representing a bidirectional connection between cell ((r_1, c_1)) and cell ((r_2, c_2)). Here, (d = 0) means the passage is open, and (1 \le d \le P) means there is a locked door of type (d).\ It is guaranteed that ((1,1)) and ((N,M)) are inside the grid.

outputFormat

Output a single integer: the minimum number of steps required for Mike to reach cell ((N,M)). If there is no valid path, output (-1).

sample

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

4