Checkers

Find the Black piece that captures every White piece in one chained jump, or report Multiple or None.

Medium5BacktrackingDFSSimulationNo attempts yetTime limit2sMemory limit256 MB

Problem

Checkers is played on an n×nn \times n board. nn is usually 8, 10, or 12, but in this problem nn is between 2 and 26. The squares of the board are colored red and black, and every piece moves only on the black squares. The two sides are called Black and White, and their pieces have the same colors. Columns are lettered from the left starting with a, and rows are numbered 1, 2, ..., nn from the bottom. Each square is named by its column letter followed by its row number, for example c6, z10, or b26. The picture below shows two boards, with extra labels for the column numbering.

A piece jumps diagonally over a piece of the other color to capture it, and the captured piece leaves the board. For a jump, the piece being jumped must be diagonally adjacent to the jumping piece, and the square directly beyond it must be empty. After a capture, if another capture is available, the same piece keeps jumping until no jump is left.

For example, on the left board the Black piece at b6 captures both White pieces in a single move. It first jumps over the White piece at c5 and lands on d4, then jumps over the White piece at e5 and lands on f6. On the right board no Black piece can jump any White piece.

It is Black's turn. Given a board, decide whether Black can capture every White piece in a single move.

Input

The first line contains the board size nn (2n262 \le n \le 26). Each of the next nn lines contains nn characters describing the board. The first of those lines is row nn, the top row, and the last one is row 1. A red square, which no piece can ever occupy, is written as .. An empty black square is _, a Black piece is B, and a White piece is W.

The board has at least one Black piece and at least one White piece. The board is always well formed: no piece sits on a red square, and the squares are colored correctly.

Output

Print, on a single line, the position of the Black piece that can capture every White piece in a single move. If more than one Black piece can do it, print Multiple. If no Black piece can do it, print None.