Checkmate
本题没有可用的提交语言。
Description
This is a chess problem. A single black king is located at some position on an otherwise empty chess board. You need to choose and place the minimum number of pieces from the standard set of $8$ white main pieces (a king, a queen, two rooks, two bishops and two knights) so that the game becomes a checkmate for black. See the note below for an explanation of the relevant chess rules.
For example, if the black king is in the $5$th square of the top row, then we can place a knight in the $7$th square of the $6$th row from the bottom and the queen in the $5$th square of the $7$th row from the bottom to achieve a checkmate for black. This is also the minimum possible number of pieces. In this problem it is not necessary to use the white king. However, if the white king is placed on the board, it must not be checked by the black king.
Chess notation. To describe the positions of the chess pieces on the board, we use the so-called algebraic chess notation. The positions of the cells of the $8 \times 8$ square chess board are described by the coordinate system where the columns are labeled with letters from a to h from left to right and the rows are numbered with integers from 1 to 8 from bottom to top. Each main piece type is denoted by a single capital letter: K for king, Q for queen, R for rook, B for bishop and N for knight. A piece on the board then is described by a string of three characters: the piece letter followed by the column and row coordinates of the location cell. For example, a rook in the $3$rd square of the $5$th row from the bottom is denoted by Rc5.
The input contains the position of the black king in the algebraic notation.
In the first line output an integer $n$, the minimum number of white pieces needed to achieve a checkmate. In the next $n$ lines, describe the positions of these pieces on the board in the algebraic notation in any order. If there are multiple solutions, output any of those.
Input
The input contains the position of the black king in the algebraic notation.
Output
In the first line output an integer $n$, the minimum number of white pieces needed to achieve a checkmate. In the next $n$ lines, describe the positions of these pieces on the board in the algebraic notation in any order. If there are multiple solutions, output any of those.
Ke8
Kc1
Kh4
2
Ng6
Qe7
2
Ra2
Rf1
2
Qg4
Kf4
Note
Pieces. There are $5$ types of main pieces in chess, kings, queens, rooks, bishops and knights. Each of these pieces is able to move in the following squares in a single move:
- a king can move to any of the squares sharing either a side or a corner with its current square;
- a queen can move to any square horizontally, vertically or diagonally in any direction;
- a rook can move to any distance horizontally or vertically;
- a bishop can move to any distance diagonally in any direction;
- a knight can move to any of the closest squares that are not in the same row, column, or a diagonal as its current square.
Checkmate. In this problem, a checkmate is a configuration of pieces on the board such that it is turn for black to move and the following conditions are true:
- the black king is in check;
- after any possible move, the black king is still in check.