9500번 - 아름다운 직사각형

세로 길이가 N, 가로 길이가 M인 직사각형이 있다. 이를 크기가 1인 정사각형 격자 N*M개로 나누기 위해 선을 그릴 수 있다. 각 정사각형 격자에는 왼쪽 위에서 오른쪽 아래로 가는 대각선과 오른쪽 위에서 왼쪽 아래로 가는 두 가지의 대각선을 그릴 수 있다. 올바른 직사각형은 각 격자에 대각선이 반드시 그려져 있다.

각 교점과 꼭짓점을 빨간색, 초록색, 파란색 증 한 가지 색상으로 색칠하려고 한다. 직사각형을 아름답게 색칠하기 위해서는 선분이 잇는 두 점은 서로 다른 색으로 색칠 되어 있어야한다. 위 조건을 만족하면서 모든 점들을 색칠 할 수 있으면 이 직사각형을 아름다운 직사각형이라고 한다.

홍준이는 아름다운 직사각형을 가지고 있었지만, 명우가 옆에서 장난을 쳐 일부 격자의 대각선 정보가 없어져서 일부 대각선 정보만 가지고 있게 되었다. 홍준이는 아름다운 직사각형을 복원하고 싶다. 홍준이를 도와 주어진 대각선 정보를 만족하면서 사전순으로 가장 앞에 있는 아름다운 직사각형을 구하자.

사전순으로 앞에 선다는 것은 정사각형 격자 각 칸의 정보를 위에서부터 오른쪽으로 읽어 문자열을 만들었을 때 그 문자열이 사전순으로 앞에 있는 것을 의미한다. 대각선은 '\' 와 '/'로 표현된다. '\'의 아스키 코드가 92고, '/'의 아스키 코드가 47이여서 '/'가 '\'보다 사전순으로 빠르다고 하자.

첫 줄에 세로 길이 N과 가로길이 M이 주어진다. (1 <= N, M <= 50) 다음 N개의 줄에 각 격자의 대각선 정보가 주어진다. 주어지는 대각선 정보 '\' 혹은 '/'이다. 만약 격자가 명우에 의해 파손되었으면 '?'가 주어진다.

만들 수 있는 아름다운 직사각형 중에 문제에서 설명한 사전순 기준으로 가장 앞에 있는 아름다운 직사각형을 입력 형식과 동일하게 N개의 줄에 출력한다. 불가능한 경우에는 "impossible"을 출력한다.