Sprinkler layout

Sara owns a rectangular farm. The farm is a grid of $5R$ rows and $5C$ columns of cells. A horizontal fence crosses the farm after every fifth row, and a vertical fence crosses the farm after every fifth column. The fences split the farm into $R \times C$ plots of size $5 \times 5$, called fields.

Birds and drought are the two problems Sara deals with. To keep birds off the crops, some fields have a scarecrow. A scarecrow occupies one cell, and a field has at most one scarecrow.

During a drought Sara waters the crops with sprinklers. Each sprinkler has one main nozzle and two side nozzles. It occupies exactly three cells and waters all three. The two side nozzles sit on cells that are orthogonally adjacent to the main nozzle. So the three cells form a straight tromino or an L tromino.

Sara wants exactly one sprinkler nozzle on every cell that does not hold a scarecrow. A scarecrow cell must not hold a nozzle. Nozzles must not sit outside the farm.

The three cells of one sprinkler may lie in neighboring fields. Then Sara must drill a hole in the fence between the two cells of that sprinkler that sit in different fields. Drilling is hard, so the arrangement must use at most $R \times C$ holes.

Given the farm, print a valid sprinkler arrangement. A valid arrangement always exists.

The first line contains two integers $R$ and $C$. $1 \le R, C \le 100$.

Then $6R-1$ lines follow, each with $6C-1$ characters. They show the fields and the fences between them. The fence is infinitely thin, but the input still writes it with characters.

Each cell is one character. A dot . is an empty cell, and # (ASCII 35) is a scarecrow. Vertical fences are | (ASCII 124), horizontal fences are -, and a fence crossing is +.

Print a grid in the same layout as the input. Mark each hole in a fence with _. Replace every empty cell . from the input with a lowercase letter a through z so that these rules hold.

1. The three cells watered by the same sprinkler share the same letter, even if they are not all in the same $5 \times 5$ field.
2. If two adjacent cells in the same field are watered by different sprinklers, they must have different letters.
3. If two adjacent cells in different fields are watered by different sprinklers and there is a hole in the fence between them, they must have different letters.
4. Adjacent cells in different fields may share a letter as long as the previous rules hold.

If several arrangements are valid, print the one obtained by processing fields in snake order. Rows are numbered from $0$. Even rows go left to right, odd rows go right to left. When a field still has a number of uncovered empty cells that is not a multiple of $3$, drill one hole to the next neighboring field in that order and lay one sprinkler through the hole so the current field becomes a multiple of $3$. Tile the rest of each field by repeatedly covering the topmost empty cell, and the leftmost one if there is a tie. Label sprinklers in the order they are placed with the earliest letter that does not break the lettering rules against already labeled neighbors. For the sample input, print the sample output exactly.

A $5 \times 5$ field with no scarecrow has $25$ cells, which is not a multiple of $3$, so it cannot be covered by sprinklers alone. A hole in the fence is needed so a sprinkler can be shared with a neighboring field. A field with a scarecrow has $24$ empty cells and can be covered inside itself.