CF1765I.Infinite Chess

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:

• each turn, the black king makes a move according to the movement rules;
• the black king cannot move to a square occupied by a white piece;
• the black king cannot move to a square which is under attack by any white piece. A square is under attack if a white piece can reach it in one move according to the movement rules;
• the white pieces never move.

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.

• a king moves exactly one square horizontally, vertically, or diagonally.
• a rook moves any number of vacant squares horizontally or vertically.
• a bishop moves any number of vacant squares diagonally.
• a queen moves any number of vacant squares horizontally, vertically, or diagonally.
• a knight moves to one of the nearest squares not on the same rank, file, or diagonal (this can be thought of as moving two squares horizontally then one square vertically, or moving one square horizontally then two squares vertically — i. e. in an "L" pattern). Knights are not blocked by other pieces, they can simply jump over them.

There are no pawns on the board.

King and knight possible moves, respectively. Dotted line shows that knight can jump over other pieces.

Queen, bishop, and rook possible moves, respectively.

黑方国王生活在一个具有无限列（竖线）和 $8$ 行（横线）的国际象棋棋盘上。列由全体整数编号（包括负数），行则编号为 $1$ 至 $8$。

初始时，黑方国王位于起始格 $(x_s, y_s)$，他需要抵达某个目标格 $(x_t, y_t)$。不幸的是，棋盘上还存在白方棋子，它们对黑方国王构成威胁。经过协商，白方棋子同意让黑方国王通行至目标格，但须满足以下条件：

• 每回合，黑方国王必须依照国际象棋规则移动；
• 黑方国王不可移至被白方棋子占据的格子；
• 黑方国王不可移至任何受白方棋子攻击的格子；若某格子可被白方棋子依照其走法一步到达，则该格子视为“受攻击”；
• 白方棋子始终静止不动。

请帮助黑方国王找出在不违反上述条件的前提下，抵达目标格所需的最少步数。黑方国王在任何时候均不得离开棋盘。

黑方国王的移动遵循如下规则。尽管白方棋子从不移动，但它们能一步到达的所有格子仍被视为“受攻击”，因此黑方国王不可进入这些格子。

以下是各棋子的移动规则。注意：除马以外，其余棋子均不可越过其他棋子。

• 王：恰好横向、纵向或斜向移动一格；
• 车：沿横向或纵向移动任意格数（路径上所有中间格必须为空）；
• 象：沿对角线移动任意格数（路径上所有中间格必须为空）；
• 后：沿横向、纵向或对角线移动任意格数（路径上所有中间格必须为空）；
• 马：移动至与其所在格最近的、既不同行、也不同列、亦不同对角线的格子之一（可理解为横向移动两格再纵向移动一格，或横向移动一格再纵向移动两格——即呈“L”形）。马不受其他棋子阻挡，可直接跃过它们。

棋盘上无兵。

王与马的可能走法（分别示意）。虚线表示马可跃过其他棋子。

后、象与车的可能走法（分别示意）。

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:

• K — king
• Q — queen
• R — rook
• B — bishop
• N — knight

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:

• no square is occupied by more than one white piece;
• the starting square for the black king is different from the square he wants to reach, and neither of these two squares is occupied or is under attack by any white piece.

第一行包含两个整数 $x_s$ 和 $y_s$（$1 \le x_s \le 10^8$；$1 \le y_s \le 8$）——表示黑王的起始坐标。

第二行包含两个整数 $x_t$ 和 $y_t$（$1 \le x_t \le 10^8$；$1 \le y_t \le 8$）——表示黑王的目标格坐标。

第三行包含一个整数 $n$（$0 \le n \le 2000$）——表示棋盘上白方棋子的数量。

接下来是 $n$ 行，其中第 $i$ 行包含一个字符 $t_i$ 和两个整数 $x_i$、$y_i$（$1 \le x_i \le 10^8$；$1 \le y_i \le 8$）——分别表示第 $i$ 个白方棋子的类型及其坐标。棋子类型的表示方式如下（均为大写拉丁字母）：

• K — 王（King）
• Q — 后（Queen）
• R — 车（Rook）
• B — 象（Bishop）
• N — 马（Knight）

棋盘上可存在任意数量的上述各类白方棋子，例如可有 $3$ 个白王或 $4$ 个白后。棋盘上没有兵（Pawn）。

输入的额外约束条件：

• 任意一格至多被一个白方棋子占据；
• 黑王的起始格与目标格不同，且这两个格子均未被任何白方棋子占据，也未受到任何白方棋子的攻击。

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$。

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.

下图展示了第二个示例的解法。其中，字母 K、R、s 和 t 分别表示白方国王、白方车、起始格和目标格。加粗的叉号标记了被白方棋子攻击的格子，加粗的圆点则标出了黑方国王的最短路径。