크로스워드 내부자

어느 신문사에 내부 제보자가 있어, 크로스워드 퍼즐의 정답 단어 목록을 당신에게 보내 줍니다. 다만 이 목록은 각 단어가 어느 자리에 들어가는지는 알려 주지 않으며, 대체로 정확하지만 가끔 오류나 누락이 있을 수 있습니다. 단어 목록과 크로스워드 격자의 모양이 주어질 때, 모든 단어를 격자에 배치하여 퍼즐 전체를 채울 수 있는지 판정하고, 가능하다면 완성된 격자를 출력하세요.

입력은 하나 이상의 문제 세트로 이루어집니다.

각 문제 세트는 두 정수 $M$과 $N$이 적힌 줄로 시작합니다. $M = 0$이고 $N = 0$인 줄은 입력의 끝을 의미하며 처리하지 않습니다. $M$은 배치할 단어의 개수로 $1 \le M \le 150$이고, $N$은 격자의 행 수로 $1 \le N \le 16$입니다.

이어서 $M$개의 줄에 각각 단어 하나가 왼쪽 정렬로 주어집니다. 모든 단어는 알파벳 문자로만 이루어지고 길이는 $2$ 이상 $16$ 이하이며, 한 문제 세트 안에서 같은 단어가 두 번 나오지는 않습니다.

그다음 $N$개의 줄에 격자 틀이 .과 # 문자만으로 왼쪽 정렬되어 주어집니다. 모든 줄의 길이는 서로 같으며 $1$ 이상 $16$ 이하입니다. .은 글자를 쓸 수 있는 칸을, #은 글자를 쓸 수 없는 칸을 뜻합니다.

각 단어는 가로(왼쪽에서 오른쪽) 또는 세로(위에서 아래)로 놓여, . 칸이 연속으로 이어진 최대 구간 하나를 정확히 가득 채워야 합니다. 모든 . 칸은 채워져야 하고 # 칸에는 글자가 들어갈 수 없습니다. 가로 단어와 세로 단어는 공통 칸에서 서로 교차할 수 있지만, 두 가로 단어(또는 두 세로 단어)는 사이에 #이 하나도 없이 맞닿거나 겹칠 수 없습니다. 목록의 각 단어는 정확히 한 번씩 사용합니다.

각 문제 세트에 대해 먼저 Problem 과 문제 세트 번호(입력에 나온 순서대로 $1$번부터)를 출력합니다.

• 유효한 배치가 존재하지 않으면 같은 줄에 이어서 : No layout is possible.을 출력합니다.
• 그렇지 않으면 다음 $N$개의 줄에 완성된 격자를 출력합니다. 즉 틀에서 모든 .을 그 자리에 놓인 글자로 바꾸고 #은 그대로 둡니다. 유효한 배치가 둘 이상이면 사전순으로 가장 작은 완성 격자를 출력합니다. 두 격자는 모든 행을 위에서 아래로, 각 행 안에서는 왼쪽에서 오른쪽으로(# 문자 포함) 읽어 비교하며, 더 작은 쪽을 택합니다.