The black king lives on a chess board with an infinite number of columns (files) and $$$8$$$ rows (ranks). The columns are numbered with all integer numbers (including negative). The rows are numbered from $$$1$$$ to $$$8$$$.
Initially, the black king is located on the starting square $$$(x_s, y_s)$$$, and he needs to reach some target square $$$(x_t, y_t)$$$. Unfortunately, there are also white pieces on the board, and they threaten the black king. After negotiations, the white pieces agreed to let the black king pass to the target square on the following conditions:
Help the black king find the minimum number of moves needed to reach the target square while not violating the conditions. The black king cannot leave the board at any time.
The black king moves according to the movement rules below. Even though the white pieces never move, squares which they can reach in one move are considered to be under attack, so the black king cannot move into those squares.
Below are the movement rules. Note that the pieces (except for the knight) cannot jump over other pieces.
There are no pawns on the board.
The first line contains two integers $$$x_s$$$ and $$$y_s$$$ ($$$1 \le x_s \le 10^8$$$; $$$1 \le y_s \le 8$$$) — the starting coordinates of the black king.
The second line contains two integers $$$x_t$$$ and $$$y_t$$$ ($$$1 \le x_t \le 10^8$$$; $$$1 \le y_t \le 8$$$) — the coordinates of the target square for the black king.
The third line contains one integer $$$n$$$ ($$$0 \le n \le 2000$$$) — the number of white pieces on the board.
Then $$$n$$$ lines follow, the $$$i$$$-th line contains one character $$$t_i$$$ and two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i \le 10^8$$$; $$$1 \le y_i \le 8$$$) — the type and the coordinates of the $$$i$$$-th white piece. The types of pieces are represented by the following uppercase Latin letters:
There can be any number of white pieces of any type listed above on the board, for example, $$$3$$$ white kings or $$$4$$$ white queens. There are no pawns on the board.
Additional constrains on the input:
Print one integer — the minimum number of moves needed for the black king to reach the target square while not violating the conditions, or $$$-1$$$ if it is impossible.
1 8 7 8 2 N 4 8 B 4 6
10
1 1 1 5 2 K 1 3 R 2 3
6
2 2 6 4 1 Q 4 3
-1
The image below demonstrates the solution for the second example. Here, the letters K, R, s, and t represent the white king, the white rook, the starting square, and the target square, respectively. Bold crosses mark the squares which are under attack by the white pieces. Bold dots show the shortest path for the black king.
Name |
---|