Squirrels Annie and Jane used to live in a very cold dwelling. So they asked their friend elephant for some ivory tiles. Tiles are rectangles with size 1sf × 2sf (1sf = one squirrel foot). Squirrels drew a plan of their room and brought it to hippo's office to ask him whether it is possible to tile their room with those tiles. But hippo was just too sleepy to think...
Write a program which for given plan of the dwelling covers it with the ivory tiles, or reports it is impossible.
The input consists of several test cases separated by blank lines. First line of each test case contains two positive integers N and M—the number of rows and columns of the plan of the dwelling, respectively. On the following N lines there is the plan consisting of a grid of dots '.' and hashes '#'. Each character represents a square of size 1sf× 1sf. A dot represents a wall and a hash represents a square of the floor to covered. Two zeros denote the end of the input.
For each test case output a grid of characters of the same dimensions as in input. Keep the walls (i.e. dots) untouched. However replace each of the characters '#' by one of the four characters 'l','r','t' or 'b'' according to whether the square is covered respectively by left, right, top or bottom square of a 1×2 (or 2×1) tile. If it is impossible to cover the entire room output a single word 'IMPOSSIBLE'. Separate the test cases by a blank line.
3 4 ..#. .##. ..#. 5 6 .##... ###### .##... .#.... .#.... 0 0Output:
IMPOSSIBLE .lr... lrlrlr .lr... .t.... .b....