Covering

Time limit2sMemory limit128 MB

Summary
Tile every X cell of a grid using unrotated 6-cell A pieces and 2-cell horizontal B pieces without overlap, printing the lexicographically smallest covering or -1 if impossible.
Level

Hard8 of 10

Topics
Dynamic programming, Backtracking, Bit manipulation, Matrix
Solved
No attempts yet

Problem

Minsik has two kinds of pieces.

Piece A (2 rows by 4 columns):

A  A
AAAA

Piece B (two horizontal cells):

BB

Neither piece may be rotated.

Youngsik has an N×M grid made up only of . and X. Each grid cell is exactly the size of one cell of a piece. Minsik wants to cover every cell marked X with the two pieces, leaving no X uncovered. Pieces may not overlap one another, and no piece may cover a . cell.

Find a way to cover all of the X cells.

Input

The first line contains the grid height N and width M, separated by a space; both are natural numbers at most 50. Each of the next N lines contains one row of the grid as a length-M string consisting only of . and X.

Output

Print the covered grid on N lines. Each cell covered by a piece is shown as that piece's letter (A or B), and every . cell stays .. If several coverings are possible, print the one that comes first in lexicographic order (if the first lines are equal, compare the second lines, then the third, and so on). If it is impossible to cover every X, print -1.

Examples5

  1. Example 1

    Input
    2 4
XXXX
XXXX
    Expected output
    ABBA
AAAA

  2. Example 2

    Input
    2 10
X..XXXX..X
XXXX..XXXX
    Expected output
    A..ABBA..A
AAAA..AAAA

  3. Example 3

    Input
    3 6
XXXXXX
XXXXXX
XXXXXX
    Expected output
    ABBABB
AAAABB
BBBBBB

  4. Example 4

    Input
    2 5
X..XX
XXXXX
    Expected output
    -1

  5. Example 5

    Input
    7 10
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXX..XXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
    Expected output
    ABBAABBABB
AAAAAAAABB
ABBABBBBBB
AAAAA..ABB
ABBAAAAABB
AAAAABBABB
BBBBAAAABB