Duck Journey Reorientation

The story revolves around a series adaptation of the Three Ducks’ Journey commissioned by Netflix. In the original scenario, the ducks start from the island marked o and travel across a grid representing ocean currents and calm seas. The currents are represented by <, >, ^, and v (which indicate movement directions: west-to‐east, east-to‐west, south‐to‐north, and north‐to‐south respectively), and calm sea areas by .. When a duck is on a cell with a current it moves one unit in the indicated direction. If the ducks step into a calm sea, go off the grid, or return to the starting island, their journey stops. The destination island is marked x.

Due to creative changes by the director, there may now be whirlpools and currents that lead off the map – which in effect have made it impossible for the ducks to reach the destination island x via the currents. Your task is to modify the grid by replacing some of the characters (<, >, ^, v, or .), while keeping the starting island o and destination island x unchanged, so that there exists a valid path from o to x using the movement rules.

The ducks are allowed to begin by moving in any of the four cardinal directions, and once they enter a cell with a current they will continue moving in the direction indicated by that cell. Make sure the modified grid allows at least one continuous journey (via currents) from the starting island to the destination island.

Note: All formulas must be given in LaTeX format. For example, the current arrow for north to south should be written as \(\to\) or with the corresponding symbol when needed.

inputFormat

The first line contains two integers \(n\) and \(m\), representing the number of rows and columns of the grid.

The next \(n\) lines each contain a string of length \(m\). The grid contains exactly one o (the starting island) and exactly one x (the destination island). Other characters in the grid are chosen from the set { <, >, ^, v, . }.

outputFormat

Output the modified grid in the same format as the input: \(n\) lines, each a string of \(m\) characters. The grid must be modified such that by starting at o and following the movement rules (using the arrows on the path), the ducks eventually reach x.

The rules for movement are:

• From the starting island o, the ducks can move one step in one of the four cardinal directions.
• If a duck lands on a cell with a current (one of <, >, ^, v), it will automatically move one unit in the indicated direction.
• The journey stops if the duck enters a calm sea cell ., goes off the grid, or revisits o.
• You cannot modify the cells containing o or x.

You may set any cell (except those containing o or x) to any character from the set {<, >, ^, v, .} as needed, and it is guaranteed that a solution exists by creating a continuous chain of currents from o to x.

sample

3 5
o....
.....
....x

o>>>v
....v
....x