E. Lizard
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Mitzi is about to leave for CODEFEM when she notices a little lizard wandering around her patio. The problem is that her $$$k$$$ chubby cats live there too.

Mitzi's patio is an $$$n \times m$$$ grid of tiles. The lizard starts on tile $$$(s_x, s_y)$$$ and can move only to the tile directly above, below, to the left, or to the right, without leaving the patio.

Each chubby cat $$$i$$$ is sitting on tile $$$(x_i, y_i)$$$ and has a jumping range $$$f_i$$$. No matter how lazy a cat may be, if the lizard is at a Manhattan distance less than or equal to $$$f_i$$$, the cat can catch it in a single leap. Therefore, the lizard will never step on a tile within the reach of any cat.

The Manhattan distance between two tiles $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ is defined as:

$$$$$$|x_1-x_2| + |y_1-y_2|$$$$$$

and represents the minimum number of moves required to travel from one tile to the other using only the four main directions.

Luckily for the lizard, there are $$$h$$$ tiles with holes in the patio where it can hide. As soon as it reaches any of them, it will be safe.

Among all holes that the lizard can reach without ever stepping on a tile within the jumping range of a cat, it will choose the one that requires the fewest moves.

If several holes can be reached using the same minimum number of moves, the lizard will choose the hole with the smallest row number. If there is still a tie, it will choose the one with the smallest column number.

Mitzi wants to know which hole the lizard will reach, so she can decide whether she can leave peacefully or needs to help it escape.

Determine the tile containing the hole the lizard will reach.

If there is no safe path to any hole, print $$$-1$$$ $$$-1$$$.

Input

The first line contains four integers $$$n$$$, $$$m$$$, $$$k$$$, and $$$h$$$ — the number of rows and columns in the patio, the number of chubby cats, and the number of tiles containing holes, respectively.

The second line contains two integers $$$s_x$$$ and $$$s_y$$$, indicating the row and column of the lizard's starting position.

Each of the next $$$k$$$ lines contains three integers $$$x_i$$$, $$$y_i$$$, and $$$f_i$$$, representing the row, column, and jumping range of the $$$i$$$-th chubby cat.

Each of the next $$$h$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$, indicating the row and column of a tile containing a hole.

The following constraints apply:

$$$1 \le n,m \le 1000$$$, $$$n \cdot m \le 5 \cdot 10^5$$$,

$$$1 \le k \le \min(2 \cdot 10^5,n\cdot m)$$$, $$$0 \le h \le \min(2 \cdot 10^5,n\cdot m)$$$,

$$$0 \le f_i \le n+m$$$, $$$1 \le s_x,x_i \le n$$$, and $$$1 \le s_y,y_i \le m$$$.

It is also guaranteed that no two chubby cats occupy the same tile, no two holes are located on the same tile, and the lizard does not start on a tile occupied by a chubby cat or on a tile containing a hole. All given positions are within the boundaries of Mitzi's patio.

Output

Print two integers $$$x$$$ and $$$y$$$, representing the row and column of the hole the lizard will reach.

If there is no path from the lizard's starting position to any hole without stepping on a tile within the jumping range of a cat, print

$$$$$$ \texttt{-1 -1}. $$$$$$

Examples
Input
7 7 3 3
1 4
2 5 0
5 2 1
6 3 2
2 1
7 4
1 7
Output
1 7
Input
3 3 1 1
3 1
2 2 1
1 3
Output
-1 -1
Note

In the first example, the lizard can reach the hole at $$$(1,7)$$$ without stepping on any tile within the jumping range of a cat.

It can reach this hole in $$$3$$$ moves:

$$$$$$ (1,4) \rightarrow (1,5) \rightarrow (1,6) \rightarrow (1,7). $$$$$$

Although other holes may also be reachable, none of them can be reached using fewer moves. Therefore, the lizard chooses the hole at $$$(1,7)$$$.

In the second example, the tiles within the jumping range of the chubby cat at $$$(2,2)$$$ prevent the lizard from reaching the hole at $$$(1,3)$$$ without stepping on a tile within the cat's jumping range.

Therefore, there is no valid path to any hole, and the answer is -1 -1.