Least Squares

You are given an irregularly-shaped area on a grid that you must cover completely with non-overlapping squares of various sizes. Doing this optimally (with the fewest number of squares) is difficult. Very difficult. Way too difficult for your limited intelligence. So I won’task. Why waste your time and mine? Instead, your much simpler task is merely to cover it with squares. That’s it. Do you think you can handle that? I have some crayons you can use. (Squares will be “coloured” by filling them with capital letters, A to Z) Oh, make sure that no touching squares have the same colour, so we can tell them apart. (Touching means sharing part of an edge; corners don’t count) Oh yes, and I’d appreciate it if you’d give me the lexicographically first configuration that satisfies this property. For simplicity’s sake. (In other words, if every row of the solved grid is concatenated into one string, give me the solution whose string would come first in a dictionary) Input Every case consists of a grid to fill with squares. The first line will contain m (0 < m ≤ 100), the number of rows in the grid, and n (0 < n ≤ 80), the number of columns. The remaining m lines will consist of a drawing of the area. A ‘?’ represents a portion of the area to be filled, while a ‘.’ represents a boundary section of the grid that you should ignore. There will be at most 100 cases. The last case will be followed by a line with two 0’s. Output For each case, output the desired coloured solution, in grid format. Separate the output of consecutive cases with a blank line. Sample Input 55 ????. ???.? ????? ????? ????. 00 Sample Output AAAB. AAA.A AAABB BBCBB BBAC.