The Kriss Kross Puzzle is a game for a single player, where there is a puzzle grid, with black and white squares, and a set of words. Basically, Kriss Kross Puzzles are solved by placing all words into the white squares of the puzzle grid, from top to bottom or from left to right. Consider a Kriss Kross Puzzle defined by: • a rectangular grid G, whose square cells are either black or white; and • a non-empty set of words W, where a word is a sequence of two or more capital letters. A solution to the Kriss Kross Puzzle is a grid S, with the same size as G, that verifies all the following conditions. • The square cells of S are either black or white. Black squares have no letters, whereas white squares have one capital letter. • The black squares of S and the black squares of G occur exactly in the same places of the corresponding grids. • Let a vertical word of S be any contiguous sequence of two or more letters that occur in a column of S (from top to bottom), that starts on the first square of the column or immediately after a black square, and that ends on the last square of the column or immediately before a black square. Similarly, let a horizontal word of S be any contiguous sequence of two or more letters that occur in a line of S (from left to right), that starts on the first square of the line or immediately after a black square, and that ends on the last square of the line or immediately before a black square. Then, every (vertical or horizontal) word of S occurs only once, and the set of all (vertical or horizontal) words of S is equal to W. Write a program that, given a Kriss Kross Puzzle with a unique solution, computes its solution. Input The first line contains an integer L (2 < L ≤ 20), which is the number of lines of the puzzle grid. The second line contains an integer C (2 < C ≤ 20), which is the number of columns of the puzzle grid. Each of the following L lines contains C characters. A character is: • either the symbol ‘0’, which represents a white square; • or the symbol ‘1’, which represents a black square. The next line contains an integer N (4 < N ≤ 100), which is the size of the set of words. Each of the following N lines contains a word. A word is a sequence of at least two capital letters, whose length does not exceed the maximum of L and C. The list of words is known to be ordered by length (smaller words appear first).
2/2 Output The output is the solution of the Kriss Kross Puzzle. It consists of L lines. Each line contains C characters, which are either a capital letter, or the symbol ‘1’ (which represents a black square). Sample Input 4 6 010001 001000 000100 010000 12 LA DO NO ON AM CAR GAS ROD MUG RULE MORE ONES Sample Output M1CAR1 ON1MUG ROD1LA E1ONES