After Holywood got its hands on the fascinating story of the successful umbrella voyage
between two islands, Netflix executives decided to make a series adaptation of the
three ducks’ travels.
As you may remember from the first round of COCI \(20/21\), the ducks have a map of
ocean currents. The ducks travel together. The island where the ducks live is marked
by the letter ’o’. The ducks can start their voyage in any of the four directions. Ocean currents in these
seas move in one of the four directions, and are marked in the following way: we\(st-ea\)st ’>’, ea\(st-we\)st
’<’, nor\(th-so\)uth ’v’ and sou\(th-no\)rth ’^’. When the ducks are located on a cell with a current, they will
move one cell in the direction of the current.
Calm sea is marked by a dot ’.’. If the currents bring the ducks to a cell with calm sea, outside the
map, or back to the starting island, they will stop their voyage. The island that the ducks want to visit is
marked by ’x’.
In order to make the series more appealing, Netflix made a few changes to the story: the sea now may
contain wild vortexes (the ducks can get stuck in a cycle) and sea currents that carry the ducks outside
the map. ^{∗}
Therefore, the original map of currents has been changed. But under heavy deadline pressure, the director
has made some mistakes: the ducks cannot arrive from the initial to the target island via sea currents
anymore.
Netflix directors are very important persons, so they don’t really spend time contemplating plot holes.
Thus it is your task now to replace as few as possible characters on the map, so that the ducks can
go from the initial to the target island.
For story purposes, the cells with (’o’ and ’x’) cannot be modified. All other cells are either sea
currents or calm sea (characters ’<>v^.’). You can replace characters in those cells with characters from
the same set ’<>v^.’.

Subtask 1 (30 points): \(3 \le r\), \(s \le 20\)

Subtask 2 (80 points): No additional constraints. If in all test cases in some subtaks the first line (minimum number of changes) is correct, but the map in some test case is not valid, you will get half of the points for that subtask.

The first line contains integers \(r\) and \(s\) (\(3 \le r\), \(s \le 2000\)), the number of rows and columns of the map.
Each of the following \(r\) lines contains \(s\) characters from the set ’o<>v^.x’, that represent the map of
ocean currents. There will always be exactly one character ’o’ and exactly one character ’x’ on the map,
and they will not be adjacent.

In the first line output \(k\), the minimum number of changes so that the ducks can go from the initial to the
target island.
In the each of the next \(r\) lines, output \(s\) characters, describing a map which differs from the input map in
exactly \(k\) cells, satisfying the requirements of the problem.
If there are multiple valid maps, output any of them.
^{∗}The ducks also form a heartbreaking love triangle, but that is not important right now.

생성자가 기록되지 않았습니다.

출처 COCI 2020/2021 Contest 4