Queens, Knights and Pawns#3456
You are all probably familiar with the famous -queens problem, in which you are asked to place queens on a chessboard so that no two queens attack each other. In this problem, you are given some queens, knights, and pawns already placed on certain squares, and you must determine how many free squares on the board are not attacked by either a queen or a knight (or both). We will call such squares "safe" squares. The board shown in the figure below has safe squares (the shaded squares are the safe ones).
Recall that a knight can move from its current position to any unoccupied square that is located at the opposite corner of a 2 \times 3 rectangle; a queen can move to any square visible along any of the eight horizontal, vertical, or diagonal directions from its current position. Note that a queen's movement may be blocked by another piece, while a knight's move cannot be blocked.
You will be given several tests. Each test consists of lines. The first line contains two integers and , which specify the size of the board, namely the number of rows and columns, respectively. Neither number will exceed . Each of the next three lines has the form
k~r_1~c_1~r_2~c_2~\ldots~r_k~c_k
specifying the number and positions of the queens, knights, and pawns, respectively. Row and column numbers start from one. The number of each piece will not exceed . A value of n = m = 0 indicates the end of input.
For each test, you must print a single line of the form
Board has safe squares.
where is the test number (starting from one), and you must supply the correct value for .
Example 1