SP32091 CSTATE2 - Chessboard State 2: International Chess Tournament

**Note: This is a harder version of CSTATE1 - a solution to this problem will (except I/O format) pass there. It is also an easier version of CSTATE3 - the solution to it will pass here.** V Slovakistane sa rozhodli osadníci usporiadať národný šachový turnaj.

The first line of the input contains the integer **1 - the number of chessboards. **t** descriptions of a chessboard follow.** The first line of each description contains two integers **8 - the length of side of the chessboard and the number of pieces currently on it.** **p** lines follow, each in the form '**x y c**' , where **1 indicate the coordinates of the chesspiece; the upper-left square has coordinates **(1,1)** while the bottom-right square is at **(n,n)**.** **c** represents the type of the chesspiece - this character is from the set **{KQRBHPkqrbhp}**, representing in this order the king, queen, rook, bishop, knight (horse), and pawn. The pieces belonging to the White player are marked by lowercase characters; the upper side of the chessboard (lower **y** coordinates) belongs to him, hence white pawns move in the positive **y** direction. The pieces belonging to the Black player are marked by uppercase characters; the lower side of the chessboard (greater **y** coordinates) belongs to him, hence black pawns move in the negative **y** direction. A blank line follows after every chessboard description. The number or placement of the pieces may by all means be impossible to reach in a game of chess, however you may assume that on every chessboard there is exactly one white king ('**k**') and one black king ('**K**'). No two pieces are on the same coordinates. Input files are 'reasonable' - that is, if a file contains a large amount of testcases, they are reasonably small. Specifically, the sum of **n+p** within an input file does not exceed **450,000**.

For each chessboard output one line with one of the following messages: - "**Safe**", if neither players' kings are being threatened - "**Impossible**", if both players' kings are being threatened - "**{colour}** **Check - m Plausible Moves**", where **{colour}** is either "**Black**" or "**White**", if the respective player's king is being threatened, and there exists **m** valid moves by his pieces after which his king is no longer threatened - "**{colour} Checkmate**", where {colour} is either "**Black**" or "**White**", if the respective player's king is being threatened, and there exists no valid move by any of his pieces after which his king is no longer threatened #### Additional note There are 16 input files "0" through "15". File 0 is the example given below. File 1 contains roughly a half of the testdata from CSTATE1; file 2 contains the rest of testdata from CSTATE1, along with some chessboards of size 100. Time limit is 2.5 seconds for each file - four times my worst time on any input file. Despite that, if you believe your solution runs just slightly longer, ping me and I might increase it. After submission you can view extra information about the result of each file by clicking the result text ("accepted","wrong answer",...), such as the result of each file and the time/memory used, but no message is present like in CSTATE1 - if you are stuck, consider submitting there for a hint at what is off in your solution.