정사각형 타일

당신은 예쁜 기하학적 그림을 팔고 있다. 이 그림은 겹치지 않는 격자위에 1 x 1 정사각형 타일이 채워진 형태이다. 예는 다음과 같다. .##.. .#### .#### .##..

여기서 '#' 문자는 파란색 타일을 뜻하고, '.'는 하얀색 타일을 뜻한다. 이 두가지 색을 제외한 다른 색을 사용해서 만들 수는 없다.

모든 사람이 파란색을 좋아하지 않기 때문에, 어떤 사람들은 모든 파란색 타일을 빨간색 타일로 바꾸고자 한다. 하지만 빨간색 타일은 2 x 2 크기의 정사각형 타일밖에 존재하지 않는다.

이 경우 당신은 파란색 타일로 이뤄진 2 x 2 의 정사각형을 하나의 빨간색 타일로 덮을 수 있으며, 더이상 덮을 수 있는 파란색 타일이 존재하지 않을 때 이를 마칠 수 있다. 또한 빨간색 타일끼리 서로 겹쳐서는 안되며, 빨간색 타일이 하얀색 타일을 덮어서도 안된다.

예를 들어 위에 나온 그림에 빨간색 타일을 덮을 경우 다음과 같이 그림이 바뀌게 된다.

./\.. .\//\ ./\\/ .\/..

빨간색 타일은 왼쪽위와 오른쪽 아래가 '/'로 문자로, 다른 두 구석은 '\' 문자로 표현이 된다. ('\'와 '\'은 같은 문자이다. 글꼴에 따라 보이는 모양이 다르다.)

파란색 타일과 하얀색 타일로 이뤄진 그림이 주어졌을 때, 이를 빨간색과 하얀색으로만 이뤄진 타일로 바꿀 수 있는지를 판단하는 프로그램을 작성하라.

입력

입력의 첫 줄에는 그림의 높이와 너비를 뜻하는 R, C가 입력된다(1≤R, C≤50). 그 다음줄 부터 R개의 줄에는 길이가 C인 '#', '.' 로 이뤄진 문자열이 입력되며, 각 줄은 해당 그림의 한 줄을 뜻한다.

출력

입력에 대해 모든 파란색을 덮도록 채울 수 없을 경우 Impossible을 출력한다. 그렇지 않을 경우 위의 두번째 그림과 같은 형태로 빨간색 타일과 하얀색 타일로 이뤄진 그림을 출력한다.

정사각형 타일 1s - MB