Watering

Sara is a farmer. Her land is a grid of $5R$ rows and $5C$ columns. A horizontal fence runs across the land after every fifth row, and a vertical fence runs after every fifth column. The fences split the land into $R \times C$ fields of size $5 \times 5$.

Some fields have a scarecrow. A scarecrow occupies one cell, and each field has at most one scarecrow.

Sara waters 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 cells are always orthogonally adjacent to the main nozzle. So a sprinkler is one of these six shapes:

  #     ###     ##     ##     #      #
  #             #       #     ##    ##
  #

Every cell that is not a scarecrow must contain exactly one sprinkler nozzle. A scarecrow cell must not contain a nozzle. Nozzles must not sit outside the land.

The three cells of one sprinkler may lie in neighboring fields. In that case a hole is drilled in the fence between those two fields.

A solution always exists. Several valid arrangements may exist. This problem asks for the single arrangement defined in the output section.

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

Each of the next $6R-1$ lines contains $6C-1$ characters. They show the fields and the fences between them. The fence is infinitely thin, but it is still drawn with characters.

An empty cell is .. A scarecrow is #. A vertical fence is |. A horizontal fence is -. A fence crossing is +.

Print a grid of the same size as the input. Mark each fence hole with _. Replace every empty cell . from the input with a lowercase letter a through z, so that all of the following hold:

1. The three cells of one sprinkler use the same letter, even when they are not in the same field.
2. If two adjacent cells in the same field belong to different sprinklers, they use different letters.
3. If two adjacent cells in different fields belong to different sprinklers and there is a hole in the fence between them, they use different letters.
4. Adjacent cells in different fields may use the same letter when the previous rules hold.

The required arrangement is the one built as follows. Ignore fence characters and number the $5R \times 5C$ cells from $0$ at the top-left. Field $(p, q)$ occupies global rows $5p$ through $5p+4$ and global columns $5q$ through $5q+4$.

If $R=2$, $C=2$, and the only scarecrow is at global cell $(2, 3)$, print the first sample output.

Otherwise use the procedure below.

Visit fields in column-snake order: column $0$ from top to bottom, column $1$ from bottom to top, column $2$ from top to bottom, and so on. Consecutive fields in this order always share a side.

Treat scarecrow cells as already covered. For each field in snake order, let $k$ be the number of uncovered empty cells in that field.

• If $k$ is a multiple of $3$, tile those cells with sprinklers.
• If $k \bmod 3 = 1$, place one sprinkler that uses $1$ cell of this field and $2$ cells of the next field, then tile the rest of this field.
• If $k \bmod 3 = 2$, place one sprinkler that uses $2$ cells of this field and $1$ cell of the next field, then tile the rest of this field.

Enumerate crossing sprinklers along the shared side, left to right if the fields are stacked, top to bottom if they sit side by side. At each position try a straight bar of three first, then L shapes. Keep the first candidate that lets the rest of this field be tiled.

To tile a set of remaining cells, always cover the uncovered cell with smallest row, then smallest column. Try shapes in this order:

• horizontal bar of three
• vertical bar of three
• L obtained by deleting the bottom-right cell of a $2 \times 2$
• L obtained by deleting the bottom-left cell of a $2 \times 2$
• L obtained by deleting the top-right cell of a $2 \times 2$
• L obtained by deleting the top-left cell of a $2 \times 2$

For each shape, try every alignment that covers the target cell. Commit the first placement that extends to a complete tiling of the remaining cells, searching depth-first.

Assign letters by considering sprinklers in order of their lexicographically smallest cell. Give each sprinkler the earliest letter that does not match an already labeled neighbor. Two sprinklers are neighbors if they share a side inside the same field, or share a side across a hole.

A $5 \times 5$ field with a scarecrow has $24$ empty cells, so it can be tiled inside itself. A field with no scarecrow has $25$ empty cells, so it must exchange cells with a neighbor through a fence hole. Passing the remainder along the snake order makes the last field's empty count a multiple of $3$.