Kattis

# Enigma

The Imitation Game is a 2014 film based in 1939 during World War II. It follows the newly created British intelligence agency MI6 as they employ Cambridge mathematics alumnus Alan Turing to crack the German Enigma machine. At the time, cryptographers everywhere believed it to be uncrackable. By the end of the film, Turing and his team were able to successfully crack the Enigma, ultimately winning the war for the allies.

If you have seen the film, you would know that, brilliant as he is, Alan Turing didn’t crack the code on his own. He employed help from his group of carefully selected colleagues. But how exactly did he select them? He placed crosswords puzzles all over Great Britain in the hopes that other brilliant minds would be able to solve them to qualify as candidates for his challenging project.

Those who solved his crosswords were given a special test to further evaluate their candidacy. Turing’s crosswords were extremely befuddling, but you are smart enough to figure out the words from the clues alone. However, you’re not really a spatial thinker, so you need some help positioning them onto the grid. Thanks to the help of modern day computing, perhaps you too can consider yourself worthy to become part of his famous team.

Given an empty crossword puzzle and a scrambled list of all of the solutions to the clues, your task is to position them appropriately on the grid. Like all typical crosswords, words are only valid when read left-right or up-down. Words must start/end either on the edge of the grid or beside a void space.

## Input

The first line of input consists of two space-separated integers, $R$ and $C$ ($1 \leq R, C \leq 21$), specifying the number of rows and columns in the crossword grid.

$R$ line follow, each of which consists of $C$ characters, specifying the grid for the unsolved crossword. Within this grid, a “#" character represents a void space (i.e. a space where no letters may be placed) and a “." character represents an empty space, where a letter should be placed.

The next line consists of a single integer $N$ ($1 \leq N \leq 200$).

$N$ lines follow, each of which consists of a single string of at least length $2$, consisting of only uppercase letters from “A" to “Z". These lines, given in no particular order, specify every word of the crossword solution that must be placed either horizontally or vertically on the grid.

## Output

Print an $R$ by $C$ grid consisting of the solved crossword.
You may assume that there will be exactly one solution in every test case.

Sample Input 1 Sample Output 1
1 15
##.........####
1
CROSSWORD

##CROSSWORD####

Sample Input 2 Sample Output 2
3 6
#.....
....##
###...
6
AT
ME
DOG
GOD
VETO
MAGIC

#MAGIC
VETO##
###DOG