题目描述

Netflix 的经商人员想要制作一个有关三只鸭子之旅的系列改编。

在 COCI20/21 的第一轮中，鸭子们位于一个洋流的地图中，鸭子们一同出行。鸭子们的起始岛屿用 o 表示。鸭子们可以往四个方向进行旅行，分别是：西 $\to$ 东（>），东 $\to$ 西（<），北 $\to$ 南（v） 和南 $\to$ 北（^）。当鸭子们位于洋流的点上时，它们将会向洋流的方向移动一个单位。

平静的海面用 . 表示。如果洋流把鸭子们带到了平静的海面、到达地图之外或者回到起始小岛处，它们就会停止旅行。鸭子们想要前往的目的地岛屿用 x 表示。

为了让情节更加吸引人，Netflix 进行了改编：现在海面上可能会出现旋涡（鸭子们可能会困在其中）和可把鸭子带到地图之外的洋流。

因此，原先地图被迫改变。但在即将到来的截止期的情况下，导演犯了几个错误：鸭子们不能再通过洋流到达目的地岛屿。

Netflix 导演是非常重要的人，因此他们并不花时间思考情节漏洞。你的任务是替换地图中的几个字符，使得鸭子们能够从起始岛屿到达目的地岛屿。

因情节需要，字符 o 和 x 不能被修改。其他字符（<>v^.）分别表示洋流和平静的海面。你可以用 <>v^. 中的任意字符来替换原先地图中 <>v^. 的任意字符。

输入格式

第一行输入两个整数 $r$ 和 $s$，分别表示地图的行数和列数。

接下来的 $r$ 行，每行包含 $s$ 个字符，字符必为 o<>v^.x 中的其中一个。保证地图上分别只有一个 o 和 x，并且它们不相邻。

输出格式

第一行输出 $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

提示

数据规模与约定

本题采用捆绑评测，自动开启 O2 优化。

Subtask	分值	数据范围及约定
$1$	$30$	$3 \le r,s \le 20$
$2$	$80$	无

对于 $100\%$ 的数据，$3 \le r,s \le 2000$。

评分方式

如果一个子任务中的所有数据中，第一行均正确，那么可以得到该子任务一半的分数。

本题启用非官方的自行编写的 Special Judge，也可以在附件中下载。欢迎大家 hack（可私信或直接发帖）。

说明

本题分值按 COCI 原题设置，满分 $110$。

题目译自 COCI2020-2021 CONTEST #4 T5 Patkice II。