题目描述

译自 COCI 2020/2021 Contest #4 T5「Patkice II」

有一片 $r\times s$ 的海域，有一只鸭子将在上面旅游。

海域每个节点的属性如下：

• o：鸭子的起始点，鸭子将选择上下左右中任意一个方向开始旅游，之后接下来的所有动作不可由鸭子本身决定。
• x：鸭子的目标点，鸭子最后要到达这个目标点。
• <：使得鸭子向左移动一格。
• >：使得鸭子向右移动一格。
• v：使得鸭子向下移动一格。
• ^：使得鸭子向上移动一格。
• .：平静的海（xian）域（jing）。

我们定义一次旅游是成功的，当且仅当：

• 鸭子不经过平静的海（xian）域（jing）。
• 鸭子不越出海域边界。
• 鸭子一旦从起始点出发，就再也不会返回起始点。
• 鸭子不能陷入如 >< 的循环。
• 鸭子最终到达了目标点。

现在我们给出了一份海域地图，但是有可能鸭子无法完成旅游。

为了使鸭子完成一次成功的旅游，您可以改动海域上的某些元素使得鸭子们的旅游成功，但不能改变起始点和目标点。

请使得改动的元素尽量少。

输出最少需要改动的元素并构造一种改动的方案。

输入格式

第一行为两个整数 $r$ 和 $s$。

接下来 $r$ 行，每行 $s$ 个字符，表示海域地图。

输出格式

第一行为一个整数 $k$，表示最少需要改动的元素个数。

接下来 $r$ 行，每行 $s$ 个字符，表示经过您改动的海域地图。

如果有多解，输出一个即可。

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

数据范围与提示

对于所有子任务，保证 $3\le r,s\le 2\times 10^3$，读入的字符均为 o、x、<、>、v、^、. 中的一个。

如果您输出的改动的元素个数正确，构造的海域地图却不正确，您只能获得该子任务一半的分数。