가리기

민식이는 다음과 같은 두 종류의 조각을 가지고 있다.

조각 A (2행 4열):

A  AAAAA

조각 B (가로 2칸):

BB

두 조각은 회전할 수 없다.

영식이는 .과 X로만 이루어진 N×M 격자를 가지고 있다. 격자의 한 칸은 조각의 한 칸이 정확히 들어가는 크기이다. 민식이는 X로 표시된 모든 칸을 두 조각으로 빈틈없이 덮으려고 한다. 조각끼리 겹쳐서는 안 되고, . 칸을 덮어서도 안 된다.

X 칸을 모두 덮는 방법을 구하여라.

첫째 줄에 격자의 세로 크기 N과 가로 크기 M이 공백으로 구분되어 주어진다. 두 값 모두 50 이하의 자연수이다. 둘째 줄부터 N개의 줄에 걸쳐 격자의 각 행이 주어지며, 각 행은 .과 X로만 이루어진 길이 M의 문자열이다.

조각으로 덮은 결과를 N개의 줄에 출력한다. 각 조각이 덮은 칸은 그 조각의 문자(A 또는 B)로, . 칸은 그대로 .으로 표시한다. 덮는 방법이 여러 가지이면 사전순으로 가장 앞서는 것을 출력한다(첫째 줄이 같으면 둘째 줄을, 그다음 셋째 줄을 비교하는 식이다). 모든 X를 덮는 것이 불가능하면 -1을 출력한다.