Programming competitions are great! Even if you don’t know any encyclopedic facts, you can still successfully solve many problems if you are smart. But that won’t be enough in this problem.
You are given a crossword puzzle. Your task is to solve it.
A crossword is a rectangular grid consisting of black and white squares, and a set of clues. Each clue is an English sentence that describes a single word. For each clue, we are also given the coordinates of a white square in the grid and a direction – either horizontally (“across”, meaning from left to right) or vertically (“down”, meaning from top to bottom). The goal is to write a letter into each white square in such a way that for each clue, we can read its solution in the grid by starting at the given square and reading in the given direction. Black squares are only used to separate the words in the grid.
Note that the clues precisely correspond to all maximal consecutive groups of two or more white squares in rows and columns of the grid. (There are no clues with 1-letter answers.)
The input file contains exactly one crossword puzzle to solve.
The first line contains two integers r and c: the number of rows and columns of the grid. Rows are numbered 0 to r − 1 starting at the top, and columns are numbered 0 to c − 1 starting on the left.
Each of the next r lines contains c characters. Hashes (“#”) represent white squares, dots (“.”) represent black squares.
The next line contains one integer a, specifying the number of clues with answers written across. Each of the next a lines contains two numbers ri and ci, and a clue. Here, (ri, ci) are the coordinates of the leftmost letter of the clue’s solution.
The next line contains one integer d, specifying the number of clues with answers written down. Each of the next d lines contains one clue in the same format as above, with (ri, ci) being the topmost letter.
The crossword has a unique correct solution.
Take the crossword from the input and replace all # characters with lowercase English letters (a-z). The output file must contain exactly r lines, each exactly c characters long.
Input:
3 4
..#.
####
..#.
1
1 0 Your favorite competition
1
0 2 Traveling salesman problem acronymOutput:
..t.
ipsc
..p.