Santo and Banto are old friends. Nevertheless, both of them being quite explosive, they sometimes start arguing.
"Apples!" cries Santo. "Pears!" shouts Banto. "I have never heard anything so silly!" replies Santo. "Apples are the only fruit worth growing on this piece of land!" We will not go into details, but only briefly explain the point. They were deciding what sort of fruit they should grow in their garden. Santo likes apple brandy, Banto likes pear brandy, but none of them was willing to give up their favorite drink and switch to something else.
Since they were not able to come to any decision, their dispute ended in court. After hearing both parties, the judge wisely decided: "The lot shall be divided into two parts of equal size and shape. Each of the two parts must be connected. Santo's part shall contain only apple trees and Banto's part only pear trees. No trees shall be cut down. Now go, both of you, and do as I said." As Santo and Banto were leaving the court room, the judge added: "And do not forget, Santo owes me a bottle of apple brandy and Banto a bottle of pear brandy from the first batch of this fall as a fee for my decision."
Santo and Banto sketched their lot, carefully noting the position of every apple and pear tree that grows there, and started to look for a suitable division.
The garden is a rectangular piece of land with size M by N meters and its area MN is even. It is divided into M by N unit squares. For each unit square, you know whether it is empty, whether it contains an apple tree, or a pear tree (there is at most one tree in each square). Divide the lot into two regions, each consisting of MN/2 unit squares, so that the first region contains no pear trees and the second contains no apple trees. The regions have to be of the same shape, i.e. the second region can be obtained by translating and rotating the first one, and they have to be connected, i.e. there has to be a path between any two squares of each region when moving only horizontally and vertically.
The input file consists of several test cases. The first line of each test case contains two numbers M and N separated by space. The next M lines contain N characters each, where "*" represents an empty square, "A" represents a square with an apple tree and "P" represents a square with a pear tree. There is a blank line after each case. The last test case is followed by a line containing two numbers 0 0, which should not be processed.
The output file should contain one possible division of the garden for each input case. For each test case, it should contain a block of M lines with N characters each. For each square, output "S" if it belongs to Santo's part (apples only), and "B" if it belongs to Banto's part (pears only). If the garden cannot be split, the block for this test case should consist of a single line with the word "NO". Output a blank line after each case.
Note: Don't worry about mailers that split long lines. We consider the first MN non-blank characters of each block, ignoring newlines inside each block.
5 6 *P**** **A*** **PA** **P*** ***A*A 6 6 ****** *A**** **A*** ****A* ***A** ****** 0 0Output:
BBBBBB SSSSBB SSBSBB SSBBBB SSSSSS NO