Description

Netflix business staff want to make an adaptation series about the journey of three ducks.

In Round 1 of COCI 20/21, the ducks were on a map of sea currents, and they traveled together. The starting island of the ducks is marked with o. The ducks can travel in four directions: west to east (>), east to west (<), north to south (v), and south to north (^). When the ducks are on a current cell, they will move one unit in the direction of the current.

A calm sea cell is marked with .. If the current brings the ducks onto a calm sea cell, outside the map, or back to the starting island, they will stop traveling. The destination island the ducks want to reach is marked with x.

To make the plot more interesting, Netflix made changes: now there may be whirlpools on the sea (the ducks may get stuck in them), and there may be currents that carry the ducks outside the map.

So the original map had to be changed. But with an upcoming deadline, the director made a few mistakes: the ducks can no longer reach the destination island via the currents.

Netflix directors are very important people, so they do not spend time thinking about plot holes. Your task is to replace a few characters in the map so that the ducks can travel from the starting island to the destination island.

For story reasons, the characters o and x cannot be modified. All other characters (<>v^.) represent currents and calm sea. You may replace any occurrence of <>v^. in the original map with any character from <>v^..

Input Format

The first line contains two integers $r$ and $s$, representing the number of rows and columns of the map.

The next $r$ lines each contain $s$ characters, each being one of o<>v^.x. It is guaranteed that there is exactly one o and one x on the map, and they are not adjacent.

Output Format

On the first line output $k$, the minimum number of characters that need to be changed.

Then output $r$ lines, each containing $s$ characters, representing the modified map.

If there are multiple valid maps, output any one of them.

3 3
>vo
vv>
x>>

1
>vo
vv>
x<>

3 6
>>vv<<
^ovvx^
^<<>>^

2
>>vv<<
^o>>x^
^<<>>^

4 4
x.v.
.>.<
>.<.
.^.o

4
x<<.
.>^<
>.<^
.^.o

Hint

Constraints

This problem uses bundled evaluation, with O2 optimization enabled automatically.

For $100\%$ of the testdata, $3 \le r,s \le 2000$.

Scoring

If, for all test cases in a subtask, the first line is correct, then you can get half of the points for that subtask.

This problem uses an unofficial self-written Special Judge. You can also download it from the attachments. Hacks are welcome (you may send a private message or post directly).

Notes

The points for this problem follow the original COCI setting, with a full score of $110$.

Translated from COCI2020-2021 CONTEST #4 T5 Patkice II.

Translated by ChatGPT 5