도미노 채우기

외계인들은 온 우주를 정복하려 한다. 그래서 이들이 가장 좋아하는 놀이가 도미노 놀이인 것도 놀랄 일이 아니다. 도미노 한 조각은 크기가 $1 \times 2$인 타일로, 두 칸 각각에 $0$부터 $9$까지의 숫자가 하나씩 적혀 있다. 놀이판은 직사각형 격자이며, 각 칸에도 $0$부터 $9$까지의 숫자가 하나씩 적혀 있다.

주어진 도미노 집합으로 놀이판 전체를 덮는 것이 목표다. 도미노는 인접한 두 칸에 놓을 수 있는데, 도미노에 적힌 두 숫자가 그 두 칸에 적힌 숫자와 같을 때에만 놓을 수 있다. 도미노는 그대로 놓거나 $90°$, $180°$, $270°$ 회전하여 놓을 수 있으므로, 두 칸에 $a$와 $b$가 적힌 도미노는 숫자가 $a$, $b$인 인접한 두 칸이라면 배치 순서에 관계없이 놓을 수 있다. 어떤 두 도미노도 겹칠 수 없으며, 주어진 각 도미노는 최대 한 번만 사용할 수 있다.

일부 칸에는 이미 타일이 놓여 있으며, 이 타일들은 그대로 두어야 한다. 주어진 도미노를 모두 놓아서, 이미 놓인 타일과 함께 놀이판의 모든 칸을 덮어야 한다.

입력에는 여러 개의 놀이 상황이 주어진다.

각 상황의 첫 줄에는 공백으로 구분된 세 정수, 즉 놀이판의 세로 길이 $M$, 가로 길이 $N$, 사용할 수 있는 도미노의 개수 $K$가 주어진다. 이때 $1 \le M \le 20$, $1 \le N \le 20$이고, $M$과 $N$ 중 적어도 하나는 짝수이며, $2 \le M \cdot N \le 110$, $1 \le K \le \lfloor M \cdot N / 2 \rfloor$이다.

둘째 줄에는 $K$개의 정수 쌍(즉 $2K$개의 정수)이 주어지며, 각 도미노에 적힌 두 숫자를 나타낸다. 어떤 두 도미노도 서로 같지 않으며, 한쪽을 $180°$ 회전하더라도 같아지지 않는다. 즉 순서를 무시한 숫자 쌍들은 서로 모두 다르다. 이미 놓여 있는 타일은 이 $K$개의 도미노에 포함되지 않는다.

이어지는 $M$개의 줄에는 각각 $N$개의 항목이 공백으로 구분되어 주어진다. $i$번째 줄의 $j$번째 항목($0 \le i < M$, $0 \le j < N$)은 대문자 X이거나 숫자 $A_{i,j}$($0 \le A_{i,j} \le 9$)이다. X는 그 칸에 이미 타일이 놓여 있음을 뜻한다.

각 상황은 빈 줄로 구분된다. 입력의 끝에는 세 개의 $0$(0 0 0)만 있는 줄이 오며, 이 줄은 처리하지 않는다.

각 놀이마다, 이미 놓인 타일과 함께 놀이판 전체를 덮도록 모든 도미노를 놓을 수 있는지 판단한다.

가능하다면, 놀이판을 $M \times N$ 격자로 출력한다. 한 줄에 한 행씩, 공백 없이 다음 문자를 사용한다.

• 가로로 놓인 도미노의 왼쪽·오른쪽 칸은 각각 [와 ],
• 세로로 놓인 도미노의 위·아래 칸은 각각 n과 u,
• 이미 놓인 타일이 덮고 있는 칸은 X.

가능한 배치가 여러 개일 수 있다. 답을 유일하게 만들기 위해 사전순으로 가장 앞서는 격자를 출력한다. 격자를 위에서 아래로, 각 행에서는 왼쪽에서 오른쪽으로 읽어 하나의 문자열로 만들고, 문자들을 ASCII 값 순서(X < [ < ] < n < u)로 비교했을 때 가장 작은 문자열이 되는 배치를 출력한다.

$M$개의 격자 행 다음에는, 다른 유효한 배치의 개수(유효한 배치의 총 개수에서 $1$을 뺀 값)를 한 줄에 출력한다.

유효한 배치가 존재하지 않으면 대신 impossible이라는 단어만 한 줄에 출력한다.

서로 다른 놀이의 결과 사이에는 빈 줄을 하나씩 출력한다.