1164번 - 가리기

민식이는 아래와 같은 두 가지 모양의 조각을 가지고 있다.

           A  A            BB
           AAAA

이 조각을 회전시키는 것은 불가능하다.

영식이는 '.'과 'X'로 이루어진 크기가 N×M인 격자를 가지고 있고, 격자의 각 칸은 '.'과 'X'로만 이루어져 있다. 격자의 한 칸은 조각의 문자 한 칸이 정확하게 들어가는 넓이이다. 민식이는 'X'가 되어있는 곳을 두 모양의 조각을 이용해 덮으려고 한다. 이때 조각을 겹치게 놓으면 안된다.

민식이가 'X'를 어떻게 가려야 하는지 구해보자.

첫째 줄에 영식이의 종이의 세로 크기 N과 가로 크기 M이 주어진다. 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 격자의 정보가 주어진다. 격자의 정보는 첫 행부터 순서대로 주어지며, '.'와 'X'로만 이루어져 있다.

N개의 줄에 민식이가 조각을 어떻게 덮어야 하는지 출력한다. 덮을 수 있는 방법이 여러 가지일 때는 사전순으로 가장 앞서는 것을 출력한다. (첫 줄이 같다면 둘째 줄을 비교하고, 그 다음 셋째 줄을 비교하고 이런 식으로) 불가능 한 경우에는 -1을 출력한다.