# DWITE Online Computer Programming Contest

## Scratch Card

November 2011
Problem 2

The economically questionable lottery business is making a mass-produced rectangular scratch card. It consists of a grid of hidden upper-case letters; you win by scratching letters so that they form a certain phrase, also consisting of upper-case letters. It might look like this one, where you would like to find the phrase “DWITEISAWESOMEHAHA”:

```DLFKJW
FKIGDT
EKIKSA
WQEDSO
MEHAHA```

You would like to mass-produce correctly scratched scratch cards to sell in the black market. To do this, you would like to have a stencil of the same size as the grid. For example, using this stencil, where “.” means “scratch” and “#” means “don’t scratch”:

```.####.
##.##.
.#.#..
.#.#..
......```

You obtain the correct solution:

```D####W
##I##T
E#I#SA
W#E#SO
MEHAHA```

Given a grid of letters and a phrase, you would like to construct a stencil to solve this puzzle. If in fact there is no solution, you should output a stencil with the letter “x” for each spot.

The input file DATA2.txt will contain 5 test cases. Each test case will begin with a line of two space-separated integers 1 ≤ H, W ≤ 10, the height and width of the grid. The next H lines will contain W upper-case letters each, describing the grid of letters. The final line of each test case will be a single string of upper-case letters, the solution string.

The output file OUT2.txt will contain 5 sets of stencils, as described above. You may assume that solutions are unique. Refer to the sample output’s format.

Sample Input (first two shown):
```5 6
DLFKJW
FKIGDT
EKIKSA
WQEDSO
MEHAHA
DWITEISAWESOMEHAHA
2 2
AB
CD
E```
Sample Output (first two shown):
```.####.
##.##.
.#.#..
.#.#..
......
xx
xx```