Knight’s Challenge on the Chessboard

F91 and Dounaisese are rivals. Dounaisese has arranged several black chess pieces on an n×n board – these include castles (C), knights (K), bishops (B), queens (Q), kings (X) and pawns (P). F91 challenges Dounaisese by controlling a white knight. The objective is to capture the black king by moving the white knight onto its square. However, the white knight must never enter a square that is under attack by any alive black piece during its journey, except in the final move when capturing the king.

Rules:

• If the white knight starts on a square that is under attack by any black piece, F91 immediately loses.
• The white knight moves using the standard L‐shaped moves (two in one direction and one perpendicular). Its possible move offsets are: \(\{(-2,-1), (-2,1), (-1,-2), (-1,2), (1,-2), (1,2), (2,-1), (2,1)\}\).
• If the white knight lands on a square occupied by a black piece, it captures that piece and the piece is removed from the board, so it no longer contributes to the attacked squares. Note: For capturing non‐king pieces, the landing square must be safe with respect to the remaining enemy pieces. The only exception is when capturing the black king: even if the king’s square is under attack by some other piece, the move succeeds.
• Black pieces have fixed positions and they do not move. Their attack ranges are determined as follows (all formulas in LaTeX):
  • Castle (C): Attacks in the four orthogonal directions until blocked. For a castle at \( (r,c) \), if \( d \) is a direction vector among \( (0,1), (0,-1), (1,0), (-1,0) \), then the attacked squares are given by \[ (r,c)+d,\; (r,c)+2d,\; \dots \quad \text{until an enemy piece is encountered.} \]
  • Bishop (B): Attacks diagonally (directions \( (1,1), (1,-1), (-1,1), (-1,-1) \)) until blocked.
  • Queen (Q): Combines the powers of the castle and bishop (all 8 directions) until blocked.
  • Knight (K): Attacks in the same L‐shaped moves as the white knight (up to 8 positions).
  • King (X): Attacks the 8 surrounding squares (adjacent horizontally, vertically, and diagonally): \[ \{(r+\delta_r, c+\delta_c) \mid \delta_r,\delta_c\in\{-1,0,1\}\setminus\{(0,0)\}\}. \]
  • Pawn (P): Attacks the two squares diagonally downward, i.e. for a pawn at \( (r,c) \), the attacked squares are \( (r+1,c-1) \) and \( (r+1,c+1) \) (assuming row 0 is the top).
• For empty moves the destination square must not be in the attack range computed from the current set of alive black pieces.

Your task is to determine the minimum number of moves required for the white knight to capture the black king. If it is impossible, output -1.

inputFormat

The first line contains three integers: n r c where n (\(1 \leq n \leq 10\)) is the size of the board, and \(r\) and \(c\) (0-indexed) represent the starting row and column of the white knight.

The next \(n\) lines each contain a string of length \(n\), representing the board. Each character is one of the following:

• . for an empty cell.
• C for a castle.
• K for a knight.
• B for a bishop.
• Q for a queen.
• X for the king (black king; there will be exactly one, the target).
• P for a pawn.

It is guaranteed that no enemy piece occupies the initial position of the white knight.

outputFormat

Output a single integer: the minimum number of moves required for the white knight to capture the black king. If it is impossible, output -1.

sample

5 0 0
.....
.....
.....
.....
....X

4