Avoiding Check Patterns

Professor Pang is given an \(n \times m\) board. Some cells are pre‐colored white or black while others are uncolored. In the board, a \(2\times2\) block of cells is said to form a check pattern if the four cells are colored in one of the following two ways:

\[ \begin{array}{cc} W & B \\ B & W \end{array} \quad \text{or} \quad \begin{array}{cc} B & W \\ W & B \end{array} \]

Note: Here, the letter W (from "wakuda" in Chewa) denotes a black cell, and B (from "biancu" in Corsican) denotes a white cell.

Your task is to fill in all uncolored cells (denoted by ?) with either W or B so that the final board does not contain any check pattern. It is guaranteed that the initial board configuration allows at least one valid coloring.

inputFormat

The first line contains two integers \(n\) and \(m\) --- the number of rows and columns of the board.

The following \(n\) lines each contain a string of length \(m\) consisting of characters W, B, or ?. The characters W and B denote already colored cells while ? denotes an uncolored cell.

outputFormat

Output \(n\) lines representing the final board after coloring all uncolored cells. Each line should be a string of length \(m\). The board must not contain any \(2 \times 2\) submatrix that forms a check pattern, i.e. one of the following patterns:

W B    B W
B W or W B

sample

3 3
???
?W?
???

WWW
WWW
WWW