Problem Description

Netflix's business personnel want to create a series adaptation about the journey of three ducks.

In the first round of COCI20/21, the ducks were located on a map of currents, traveling together. The starting island for the ducks is denoted by 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 point of the current, they will move one unit in the direction of the current.

Calm sea surfaces are denoted by .. If the current carries the ducks to a calm sea, outside the map, or back to the starting island, they will stop traveling. The destination island for the ducks is denoted by x.

To make the plot more engaging, Netflix has adapted the scenario: now, whirlpools (which can trap the ducks) and currents that can take the ducks off the map may appear.

Therefore, the original map had to be changed. However, given the upcoming deadline, the director made several mistakes: the ducks can no longer reach the destination island via the currents.

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

Due to the plot requirements, the characters o and x cannot be modified. Other characters (<>v^.) represent currents and calm seas. You can replace any character in the original map that is one of <>v^. with any character from <>v^..

Input Format

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

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

Output Format

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

The next $r$ lines should each contain $s$ characters, representing the modified map.

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

Sample Input and Output

Sample Input #1

3 3
>vo
vv>
x>>

Sample Output #1

1
>vo
vv>
x<>

Sample Input #2

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

Sample Output #2

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

Sample Input #3

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

Sample Output #3

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

Notes/Hints

Data Size and Constraints

This problem is bundled and automatically enables O2 optimization.

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

Scoring Method

If the first line is correct for all data in a subtask, you can get half the score for that subtask.

This problem uses a non-official custom Special Judge, which can also be downloaded from the attachments. Everyone is welcome to hack (can be done via private message or directly posting).

Notes

The score for this problem is set according to the original COCI problem, with a maximum score of $110$.

The problem is translated from COCI2020-2021 CONTEST #4 T5 Patkice II.

见题面 Input 部分

见题面 Output 部分