사다리꼴 퍼즐

정육각형의 마주 보는 세 쌍의 변 사이마다 등간격 평행선을 $2n-1$개씩 그으면 정육각형이 정삼각형으로 나뉜다. 이렇게 만든 것을 크기 $n$인 육각형 퍼즐이라고 한다. 퍼즐의 삼각형 중 일부는 색칠되어 있고, 색칠된 삼각형은 퍼즐 조각으로 덮어야 한다. 조각은 정삼각형 세 개를 나란히 붙인 사다리꼴이다. 조각의 색은 1부터 6까지의 번호로 나타내는 6가지이고, 색마다 조각을 무한히 많이 쓸 수 있다.

그림 1: 첫 번째 예제의 크기 3인 퍼즐과 이를 덮는 한 가지 방법.

다음 조건을 모두 만족하도록 조각을 육각형 위에 놓아야 한다.

1. 각 조각은 색칠된 삼각형 세 개를 완전히 덮는다.
2. 색칠된 삼각형은 각각 정확히 하나의 조각으로 덮인다.
3. 같은 색의 두 조각은 삼각형의 변을 따라 맞닿지 않는다. (꼭짓점에서 만나는 것은 괜찮다.)

퍼즐을 풀 수 있는지 판단하고, 풀 수 있다면 아래 출력 형식에서 정한 풀이를 구하라.

첫째 줄에 퍼즐의 크기를 나타내는 양의 정수 $n$이 주어진다. ($1 \le n \le 5$)

다음 $2n$개의 줄에는 퍼즐의 행이 위에서 아래 순서로 주어진다. 각 줄은 한 행의 삼각형을 왼쪽에서 오른쪽 순서로 나타낸 문자열이다. 숫자 0은 색칠된 삼각형, .(점)은 색칠되지 않은 삼각형이다. 행의 길이는 위에서부터 차례로 $2n+1, 2n+3, \ldots, 4n-1, 4n-1, \ldots, 2n+3, 2n+1$이다. 한 행 안에서 삼각형의 방향은 번갈아 바뀐다. 위쪽 $n$개 행은 첫 삼각형이 위를 향하고, 아래쪽 $n$개 행은 첫 삼각형이 아래를 향한다.

색칠된 삼각형은 적어도 하나 있다.

퍼즐을 풀 수 없으면 첫째 줄에 nemoguce(크로아티아어로 "불가능")를 출력한다.

풀 수 있으면 풀이를 입력과 같은 형식의 $2n$개 줄로 출력한다. 색칠된 삼각형은 0 대신 그 삼각형을 덮는 조각의 색을 1부터 6까지의 숫자로 쓰고, 색칠되지 않은 삼각형은 . 그대로 둔다.

답이 하나로 정해지도록 조각의 배치와 색은 다음 규칙을 따른다. 삼각형의 읽는 순서란 행을 위에서 아래로, 한 행 안에서는 왼쪽에서 오른쪽으로 보는 순서이다.

1. 색칠된 삼각형을 읽는 순서대로 훑는다. 아직 덮이지 않은 색칠된 삼각형을 만나면, 그 삼각형이 읽는 순서로 가장 앞선 칸이 되는 새 조각을 놓는다. 이렇게 놓을 수 있는 조각 가운데 남은 색칠된 삼각형을 모두 덮을 수 있는 상태가 유지되는 조각만 후보가 된다. 후보 중에서 읽는 순서로 두 번째 삼각형이 가장 앞선 조각을 고르고, 그것이 같으면 세 번째 삼각형이 가장 앞선 조각을 고른다.
2. 조각을 놓은 순서대로 색을 정한다. 각 조각에는 삼각형의 변을 공유하는 먼저 놓인 조각들이 쓰지 않은 가장 작은 색 번호를 준다. 한 조각은 변을 따라 최대 5개의 조각과 맞닿으므로 이런 색은 항상 존재한다.

그림 1의 풀이는 가능한 풀이 중 하나일 뿐이며 위 규칙이 정하는 답과 다를 수 있다.