408356: GYM103104 G Crossword Puzzle

The Riddle Man is a crossword enthusiast who has a very unique crossword solving technique, so he can always solve puzzles very quickly. Today, the Riddle Man is doing a crossword puzzle with some bugs, he wants you to help him check his process, otherwise he won't tell you the meaning of the sign-in question.

A crossword is a word puzzle that usually takes the form of a rectangular grid of white- and black-shaded squares. The game's goal is to fill the white squares with letters, forming words or phrases, by solving clues, which lead to the answers. In languages that are written left-to-right, the answer words and phrases are placed in the white-shaded grid from left to right ("Across") and from top to bottom ("Down"). The black-shaded squares are used to separate the words or phrases.

The clues are given outside the grid, divided into an Across list and a Down list; the first cell of each entry contains a number referenced by the clue lists. For example, the answer to a clue labeled "17 Down" is entered with the first letter in the cell numbered 17, proceeding down from there. The numbered cells are numbered in the upper left corner of the cell and are numbered consecutively.

The Riddle Man is very good at solving clues, so he always guessed the answers to each clue and then tried to fill it in the squares. However, today's crossword puzzle is a little more difficult for the Riddle Man, so he has multiple possible answers to some clue and isn't sure which one is correct. So, your task is to help the Riddle Man check whether the answers he gives can complete the crossword puzzle, or in other words, fill every white grid with them. Since the Riddle Man is lazy, he also wants your program to output the final result of the puzzle for him, if his candidate answers complete the puzzle correctly.

The Riddle Man's anagrams will be presented in the form of character graphs. Recall that, the map of a word puzzle is a square or a rectangular grid of white- and black-shaded squares. Each grid is represented by a character picture of $$$5 \times 5$$$, characters '$$$\text{-}$$$' said its lateral border, and ' $$$\text{|}$$$ ' said its longitudinal border. For Black-Shaded Squares, the $$$3 \times 3$$$ area in the center is filled with character '$$$\text{*}$$$'; while the white grid is filled with spaces. In particular, for a white grid with number label, the number label is always in the upper left corner of the center area. For an answer-filled cell, the letter of the answer should always be in the center of the cell, and its number label is hidden if it has one. In addition, adjacent squares will share characters on the boundary. Examples are as follows:

Note that a valid candidate answer should be the same length as its clue.

The first line of input contains four integers, $$$H, W, N$$$, and $$$M \; (1 \leq H,W \leq 500, \, 1 \leq N+M <1000)$$$, indicating that the riddle consists of $$$H \times W$$$ squares with $$$N$$$ horizontal clues and $$$M$$$ vertical clues.

The next $$$4H+1$$$ lines, each contains $$$4M+1$$$ characters (not including newline characters), represent the crossword map given by the Riddle Man;

Next $$$N$$$ lines, each line begins with two integers $$$a_i, c_i \; (1\leq a_i \leq N+M, \, c_i \in \{1, 2\})$$$, $$$a_i$$$ represents the label of the $$$i^{\rm{th}}$$$ horizontal clue, $$$c_i$$$ is the number of candidate answer for this clue by the Riddle Man. Then there are $$$c_i$$$ strings, containing only uppercase English letters, with each string representing a candidate answer. The length of a candidate answer is at least $$$2$$$ and will not exceed $$$500$$$.

Next $$$M$$$ lines, each line begins with two integers, $$$d_i, c_i \; (1\leq d_i \leq N+M, \, c_i \in \{1, 2\})$$$, $$$d_i$$$ represents the label of the $$$i^{\rm{th}}$$$ vertical clue, $$$c_i$$$ has the same meaning as before, and the following $$$c_i$$$ strings have the same restriction.

If the candidate answers provided by the Riddle Man can not complete the puzzle correctly, print $$$\text{No}$$$. Otherwise print $$$\text{Yes}$$$, and then print $$$4H+1$$$ lines of $$$4M+1$$$ characters per line (not including newline characters), representing the answer to the puzzle.

It is guaranteed that there is at most one solution to the given crossword puzzle.

4 5 3 2
---------------------
|***|***|1  |***|***|
|***|***|   |***|***|
|***|***|   |***|***|
---------------------
|***|2  |   |   |   |
|***|   |   |   |   |
|***|   |   |   |   |
---------------------
|3  |   |   |***|***|
|   |   |   |***|***|
|   |   |   |***|***|
---------------------
|***|   |***|4  |   |
|***|   |***|   |   |
|***|   |***|   |   |
---------------------
2 2 SOLD HOLD
3 2 WHU HIS
4 1 AC
1 2 YOUR YOU
2 2 SHE HER

Yes
---------------------
|***|***|   |***|***|
|***|***| Y |***|***|
|***|***|   |***|***|
---------------------
|***|   |   |   |   |
|***| S | O | L | D |
|***|   |   |   |   |
---------------------
|   |   |   |***|***|
| W | H | U |***|***|
|   |   |   |***|***|
---------------------
|***|   |***|   |   |
|***| E |***| A | C |
|***|   |***|   |   |
---------------------

3 7 2 2
-----------------------------
|***|***|2  |***|***|***|4  |
|***|***|   |***|***|***|   |
|***|***|   |***|***|***|   |
-----------------------------
|1  |   |   |***|3  |   |   |
|   |   |   |***|   |   |   |
|   |   |   |***|   |   |   |
-----------------------------
|***|***|   |***|***|***|   |
|***|***|   |***|***|***|   |
|***|***|   |***|***|***|   |
-----------------------------
1 2 DDC ABC
3 2 CEO WAS
2 2 ACE MVP
4 2 LOVE PVP

No