在好莱坞获得了关于两岛之间成功伞航的迷人故事后，Netflix 的高管们决定将这三只小鸭子的旅行改编成一部电视剧。

正如你可能还记得 COCI 20/21 第一轮中的内容，小鸭子们有一张洋流图。小鸭子们一起旅行。小鸭子们居住的岛屿用字母 'o' 标记。小鸭子们可以向四个方向中的任意一个方向开始他们的航行。这些海域中的洋流向四个方向之一移动，并按以下方式标记：自西向东为 '>'，自东向西为 '<'，自北向南为 'v'，自南向北为 '^'。当小鸭子们位于有洋流的单元格时，他们将沿着洋流的方向移动一个单元格。

平静的海面用点 '.' 标记。如果洋流将小鸭子们带到平静海面的单元格、地图外或回到起点岛屿，他们将停止航行。小鸭子们想要访问的岛屿用 'x' 标记。

为了让这部电视剧更具吸引力，Netflix 对故事做了一些改动：海面现在可能包含狂野的漩涡（小鸭子可能会陷入死循环）以及将小鸭子带出地图的洋流。*

因此，原始的洋流图已被改变。但在紧迫的截止日期压力下，导演犯了一些错误：小鸭子们再也无法通过洋流从起点岛屿到达目标岛屿了。

Netflix 的导演们都是非常重要的人物，所以他们并没有真正花时间去思考剧情漏洞。因此，你现在的任务是修改地图上尽可能少的字符，使得小鸭子们能够从起点岛屿到达目标岛屿。

出于剧情需要，含有（'o' 和 'x'）的单元格不能被修改。所有其他单元格要么是洋流，要么是平静的海面（字符为 '<>v^.'）。你可以将这些单元格中的字符替换为同集合 '<>v^.' 中的字符。

* 小鸭子们还陷入了一段令人心碎的三角恋，但现在这并不重要。

输入格式

第一行包含整数 $r$ 和 $s$（$3 \le r, s \le 2000$），表示地图的行数和列数。

接下来的 $r$ 行，每行包含 $s$ 个来自集合 'o<>v^.x' 的字符，代表洋流地图。地图上将始终有且仅有一个字符 'o' 和一个字符 'x'，且它们不会相邻。

输出格式

第一行输出 $k$，即为了让小鸭子能从起点岛屿到达目标岛屿所需的最少修改字符数。

接下来的 $r$ 行，每行输出 $s$ 个字符，描述修改后的地图。该地图与输入地图相比，恰好有 $k$ 个单元格不同，且满足题目要求。

如果有多个合法的地图，输出其中任意一个。

子任务

如果在某个子任务的所有测试用例中，第一行（最少修改次数）均正确，但某些测试用例中的地图不合法，你将获得该子任务一半的分数。

样例

输入样例 1

3 3
>vo
vv>
x>>

输出样例 1

1
>vo
vv>
x<>

输入样例 2

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

输出样例 2

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

输入样例 3

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

输出样例 3

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