Travelling worm P46641

A worm moves on an n × m board, keeping the direction of its movement while possible. The worm cannot go out of the board, nor cross any obstacle, nor cross any square visited before. In these cases, the worm turns the direction of its movement 90 degrees to the right. If, even after turning 90 degrees, the worm cannot continue, it stops.

Implement a program that prints the squares visited by the worm. The worm starts in the central position of the board, moving upwards.

Input

Input consists of the description of the board. The first line contains the number of rows n and the number of columns m, both odd numbers greater than 2. Follow n lines, each with m characteres. A ‘.’ indicates a free position. An ‘*’ indicates an obstacle. The central position is always free.

Output

Print the board with a ’G’ on each position visited by the worm.