크로스워드 퍼즐 채우기

어느 지역 소식지에서 매 호마다 크로스워드 퍼즐을 싣기로 했습니다. 편집자들은 완성된 퍼즐을 사서 쓰는 대신, 원하는 모양과 직접 고른 단어들로 퍼즐을 만들고 싶어 합니다. 그래서 프로그래머인 여러분에게 이 문제를 맡겼고, 여러분은 이를 컴퓨터로 한 번에 해결하기로 했습니다.

크로스워드 격자는 다음과 같이 생겼습니다.

..#......
#.#......
#########
#.#.#...#
#.#.....#
######..#
#.#......

가로 또는 세로로 # 이 2개 이상 연속된 구간은 각각 하나의 단어를 나타내며, 칸 하나에 글자 하나가 들어갑니다. 가로 단어와 세로 단어가 겹치는 칸에서는 두 단어가 그 위치에서 같은 글자를 가져야 합니다.

여러분이 만들 프로그램은 주어진 격자를 주어진 단어 집합으로 다음 조건을 모두 만족하도록 채워야 합니다.

• 격자의 모든 # 칸에는 정확히 글자 하나가 들어간다.
• 그 외의 칸(.)에는 글자가 들어가지 않는다.
• 단어 목록의 모든 단어가 격자에 정확히 한 번씩만 나타나며, 사용되지 않고 남는 단어가 없다.
• 단어 목록에 없는 단어(또는 그 밖의 글자열)가 격자에 나타나지 않는다.

더 긴 단어 안에 우연히 포함되는 부분 단어(예: BRIGHTLY 안의 BRIGHT)는 그 단어의 출현으로 세지 않습니다. 각 퍼즐 안에서 단어 목록의 단어는 모두 서로 다르다고 가정해도 되며, 주어진 격자와 단어 목록에 대해 가능한 배치는 많아야 하나뿐이라고 가정해도 됩니다.

입력의 첫 줄에는 데이터셋의 개수를 나타내는 정수가 주어집니다. 각 데이터셋의 첫 줄에는 두 정수 w h ($2 \le w, h \le 15$)가 주어지며, w 는 퍼즐의 너비, h 는 높이입니다. 이어지는 h 개의 줄에는 위에서 설명한 형식의 크로스워드 격자가 주어집니다. 퍼즐 안의 모든 단어 구간은 길이가 2 이상입니다. 그다음 줄에는 단어의 개수를 나타내는 정수 c ($1 \le c \le 100$)가 주어지고, 이어지는 c 개의 줄에 단어 목록이 한 줄에 하나씩 주어집니다.

각 데이터셋마다 먼저 Puzzle #x 라는 제목 줄을 출력합니다. 여기서 x 는 첫 번째 데이터셋이면 1, 두 번째면 2, 와 같이 1부터 시작하는 순번입니다. 그 아래에, 주어진 격자와 단어 목록으로 퍼즐을 완성할 수 없으면 I cannot generate this puzzle. 를 출력하고, 완성할 수 있으면 채워진 격자를 출력합니다. 채워진 격자는 원래 격자와 같은 h 줄이며 각 줄은 w 글자로 이루어집니다. 각 # 칸은 그 칸에 배정된 글자로 바뀌고, 각 . 칸은 그대로 . 로 남습니다.