Sprinkler Layout

Sara farms a large rectangular piece of land. The land is a grid of $5R$ rows and $5C$ columns. A horizontal fence crosses the land after every fifth row and a vertical fence crosses it after every fifth column, so the fences cut the land into $R \times C$ areas of $5 \times 5$ cells called fields.

Birds eat the crops, so some fields have a scarecrow. A scarecrow takes one cell, and a field holds at most one scarecrow.

During a drought Sara waters the crops with sprinklers. A sprinkler has one main nozzle and two side nozzles. The main nozzle takes one cell, and the two side nozzles take two different cells that touch the main nozzle from above, from below, from the left, or from the right. A sprinkler therefore takes three cells and waters all three of them.

Sara wants exactly one nozzle on every cell that has no scarecrow. A cell with a scarecrow takes no nozzle, and no nozzle may lie outside the land.

The three cells that one sprinkler waters need not lie in the same field. When they reach into a neighboring field, Sara drills a hole in the fence between the two cells.

Given the land, print an arrangement of sprinklers.

The first line contains two integers $R$ and $C$ ($1 \le R, C \le 100$), the size of the land.

Then $6R-1$ lines follow, each with $6C-1$ characters. They describe the land and the fences between the fields. The fence is infinitely thin, but it still takes one character in the picture.

One cell is one character. An empty cell is . and a cell with a scarecrow is #. A vertical fence is |, a horizontal fence is -, and a crossing of two fences is +.

A field holds at most one scarecrow. The data is such that the procedure described in the output section runs to the end.

Print $6R-1$ lines of $6C-1$ characters, showing the land with the sprinklers in the same format as the input. Keep # on every cell with a scarecrow, replace every empty cell with a lowercase letter from a to z, and replace the fence character with _ at every hole. The arrangement satisfies these four rules.

1. The three cells that one sprinkler waters carry the same letter, even when they do not all lie in the same field.
2. When two cells that touch inside one field are watered by different sprinklers, they carry different letters.
3. When two cells that touch across a fence are watered by different sprinklers and the fence between them has a hole, they carry different letters.
4. Two cells that touch across a fence may carry the same letter as long as the rules above hold.

Several arrangements can satisfy the rules, so print the one that this procedure builds. Rows are counted from the top and columns from the left.

Read the cells from top to bottom, and from left to right inside a row. When you reach a cell $(r, c)$ that has no scarecrow and that no sprinkler waters yet, put a sprinkler on it. Use the first shape in this list whose three cells all lie inside the land, hold no scarecrow, and take no water yet.

1. $(r, c)$, $(r, c+1)$, $(r, c+2)$
2. $(r, c)$, $(r, c+1)$, $(r+1, c)$
3. $(r, c)$, $(r, c+1)$, $(r+1, c+1)$
4. $(r, c)$, $(r+1, c)$, $(r+1, c+1)$
5. $(r, c)$, $(r+1, c-1)$, $(r+1, c)$
6. $(r, c)$, $(r+1, c)$, $(r+2, c)$

Drill a hole in every fence character that separates two cells watered by the same sprinkler, and leave every other fence character as it is. A + is never a hole.

Number the sprinklers in the order you place them. Going in that order, give each sprinkler the first letter from a to z that keeps rules 2 and 3 against the sprinklers that already carry a letter.