Suppose that you have a rectangular field that is *L* meters
long and *W* meters wide. Let us think of this as an *L* by *W*
grid of squares, where each square is 1 meter by 1 meter. Some
of these squares have trees growing within them (shown as black
circles in the figure below).

Your have a meter square lawn mower. You may move this
lawn mower up, down, left, or right by one meter so long as: (1) the
lawn mower lies entirely within the rectangular field, and (2) the
lawn mower never overlaps a square containing a tree. The lawn mower
*cannot* be rotated and *cannot* be picked up and moved over
a tree.

The lawn mower can ``reach'' a grid square if there is some way to move the lawn mower from its original position so that it entirely covers this square. Your task is to determine which squares of the lawn can be reached by the lawn mower. This region is shaded in the figure above on the right.

The first line of the input contains two positive integers,
the length and width, *L* and *W* of the field. You may assume
that length and width are at most 40. Each of the next *L* lines
contains *W* *marker characters*, where each marker character
corresponds to a grid square.

The marker character `+' means that there is a tree here, `.' means
no tree. `M' is the *center* of the initial position of the
lawn mower. (So initially the lawn mower overlaps this square and
the 8 squares immediately surrounding it.) You may assume that
there is exactly one `M', and initially the lawn mower is in a
legal position (that is, it does not overlap any trees).

To aid readability, each marker character is preceded by a single space.

The output consists of *L* lines, each containing *W* marker
characters, and each marker character is preceded by a single space.
The character `+' signifies a tree, `O' (capital letter `Oh') is
a square that the lawn mower can touch, and `.' is a square that
the lawn mower cannot reach. The input and output for the above
example is given below.

Input: | Output: |
---|---|

12 11 . . . . . . . . . . . . . . + . . . . . + . . . . . . . . . . . . . . . . . . . . . . . . + . . . . . . . . . . . . + . . . . . . . . + . . . M . . . . . . . . . . . . . . + . . . + . . . . . . . + . . . . . . + . . . . . . . . . . . . . . . . . . . . . + . . . . |
12 11 . . . . O O O O O . . . . . + O O O O O + . . . O O O O O O O O O . . O O O O O O O O O . + O O O O O O O O O . . . + O O O O O O O . + . O O O O O O O O . . . O O O O O O + . . . + O O O O O O . + O O O O O O + . . . . O O O O O O . . . . . O O O O O O + . . . . |

Input 1 | Output 1 |
---|---|

Input 2 | Output 2 |

Input 3 | Output 3 |

Input 4 | Output 4 |

Input 5 | Output 5 |

Mon Mar 17 14:34:34 EST 1997