You have an infinite number of the following two polyominoes:
A A AAAA
You are NOT allowed to rotate them.
You are given a String region that represents a rectangular table filled with characters '.' and 'X'. The j-th character of the i-th element of region represents the cell at row i, column j of the table.
You need to cover (without overlapping) all the 'X' characters with the given polyominoes. Return a String that contains the same area with cells marked '.' left untouched, and cells marked 'X' changed to 'A' or 'B', according to the polyomino that covers the cell.
If there is no solution, return an empty String.
If there are multiple solutions, return the one among them that comes first lexicographically. That is, you must minimize the first string, if there are still several solutions, minimize the second one, and so on.
|-||A string S is greater than a string T lexicographically if T is a proper prefix of S, or if S has a greater character at the first position where the strings differ.|
|-||region will contain between 1 and 50 elements, inclusive.|
|-||Each element of region will contain between 1 and 50 characters, inclusive.|
|-||All elements of region will contain the same number of characters.|
|-||Each character in each element of region will be either '.' or uppercase 'X'.|