题目描述

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

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

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

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

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

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

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

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

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

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

输入格式

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

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

输出格式

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

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

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

样例 1

输入 3 3

vo vv> x>>

text

输出 1

vo vv> x<>

text

样例 2

输入 3 6

vv<< ^ovvx^ ^<<>>^

text

输出 2

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

text

样例 3

输入 4 4 x.v. .>.<

.<. .^.o

text

输出 4 x<<. .>^<

.<^ .^.o

text

数据范围与提示

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

子任务编号	约束	分值
1	$3 \le r,s \le 20$	$30/110$
2	无特殊限制	$80/110$

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