Velociraptor is fit P22437

When a velociraptor does not smell human blood, takes advantage to do some exercise and mark its territory. In a rectangular room n × m with obstacles, our friend starts running trying to keep the direction and the sense of its movement while it is possible, leaving a pheromone trace. Under any circumstances it will go out of the room, nor will cross an obstacle, nor will cross a square that was crossed previously. In these cases, velociraptor will turn 90 degrees to the right. If, even turning 90 degrees, the velociraptor could not continue, it would stop.

Implement a program that prints the squares where the velociraptor has been before stopping. The velociraptor always starts in the central position of the room, moving towards north.

Input

The input describes a room. The first line has the number of rows n and the number of columns m. It is fulfilled that 2 < n, m < 200. n as well as m are odd numbers. n lines follow, with m characters each one. An asterisk indicates an obstacle. The central position is always free.

Output

Your program must print the board with a ’V’ in each position where the velociraptor has been.