캡슐 퍼즐

컴퓨터를 공부하다 보면 한 번쯤 스도쿠 풀이 프로그램을 짜게 된다. 이 문제도 격자에 수를 채우는 퍼즐이다.

굵은 선으로 나뉜 각 영역에는 $1$부터 $n$까지의 수를 하나씩 넣는다. $n$은 그 영역에 속한 칸의 개수다. 같은 수끼리는 맞닿을 수 없고, 대각선으로 닿는 것도 안 된다. 즉 변이나 꼭짓점을 공유하는 두 칸에는 서로 다른 수가 들어간다.

일부만 채워진 격자	완성된 격자

일부만 채워진 격자를 입력받아 완성된 격자를 출력하는 프로그램을 작성한다.

첫 줄에 데이터 집합의 개수 $P$ ($1 \le P \le 100$)가 주어진다. 각 데이터 집합은 독립적으로 처리한다.

각 데이터 집합의 첫 줄에는 데이터 집합 번호 $K$ ($1 \le K \le 100$), 격자의 행 수 $R$ ($1 \le R \le 7$), 열 수 $C$ ($1 \le C \le 7$)가 공백으로 구분되어 주어진다. 이어지는 $R$개의 줄에 격자가 한 줄에 한 행씩 주어지며, 각 줄에는 $C$개의 항목이 공백으로 구분되어 있다. 항목은 그 칸에 이미 놓인 숫자이거나, 빈 칸을 뜻하는 -다.

그 다음 줄에는 영역의 개수가 주어진다. 이어지는 각 줄은 영역 하나를 나타낸다. 먼저 영역에 속한 칸의 개수 $N$이 오고, 그 뒤에 $N$개의 칸 표기가 공백으로 구분되어 온다. 칸 표기는 여는 괄호, 행 번호, 쉼표, 열 번호, 닫는 괄호 순서다. 행 번호는 위에서 아래로 $1$부터 $R$까지, 열 번호는 왼쪽에서 오른쪽으로 $1$부터 $C$까지다.

영역은 격자를 빠짐없이 나누므로 모든 칸은 정확히 하나의 영역에 속한다. 한 영역의 칸 수는 $9$를 넘지 않아 모든 값은 한 자리 숫자다. 각 데이터 집합에는 답이 적어도 하나 존재한다.

각 데이터 집합마다 데이터 집합 번호 $K$를 한 줄에 출력하고, 이어서 완성된 격자를 $R$개의 줄에 출력한다. 각 줄에는 $C$개의 숫자를 공백 하나로 구분해 출력한다.

완성된 격자가 여러 개인 데이터 집합에서는 사전순으로 가장 작은 것을 출력한다. 두 격자를 비교할 때는 위에서 아래로, 각 행에서는 왼쪽에서 오른쪽으로 숫자를 늘어놓고, 처음으로 달라지는 자리에서 더 작은 숫자가 오는 쪽을 택한다.