You have an infinite number of the following two polyominoes: AAAA and BB.
You are given a String region, filled with characters '.' and 'X'. You need to cover (without overlapping) all the 'X' characters with the given polyominoes.
Return a String that contains the same region 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 the String "impossible" (quotes for clarity only).
If there are multiple solutions, return the lexicographically smallest one.