#1999 정사각형 타일

27  1 s   128 MB  

Description

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

    
.##..
.####
.####
.##..

여기서 '#' 문자는 파란색 타일을 뜻하고, '.'는 하얀색 타일을 뜻한다. 이 두가지 색을 제외한 다른 색을 사용해서 만들 수는 없다. 모든 사람이 파란색을 좋아하지 않기 때문에, 어떤 사람들은 모든 파란색 타일을 빨간색 타일로 바꾸고자 한다. 하지만 파란색 타일은 2 x 2 크기의 정사각형 타일밖에 존재하지 않는다. 이 경우 당신은 파란색타일로 이뤄진 2 x 2 의 정사각형을 하나의 빨간색 타일로 덮을 수 있으며, 더이상 덮을 수 있는 파란색 타일이 존재하지 않을 때 이를 마칠 수 있다. 또한 빨간색 타일끼리 서로 겹쳐서는 안되며, 빨간색 타일이 하얀색 타일을 덮어서도 안된다. 예를 들어 위에 나온 그림에 빨간색 타일을 덮을 경우 다음과 같이 그림이 바뀌게 된다

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

빨간색 타일은 왼쪽위와 오른쪽 아래가 '/' 로 문자로, 다른 두 구석은 '\\' 문자로 표현이 된다. 빨간색 타일과 하얀색 타일로 이뤄진 그림이 주어졌을 때, 이를 빨간색과 하얀색으로만 이뤄진 타일로 바꿀 수 있는지를 판단하는 프로그램을 작성하라.

Input

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

Output

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

Sample Input

Sample Output

2 4
.###
.###
Impossible

Sample Input 2

4 5
.##..
.####
.####
.##..

Sample Output 2

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