题目描述

奥勒讨厌叉。它们让他想起在 OI 比赛的时候看到满屏的「Wrong Answer」。当他到达瓦尔哈姆拉冰场，看到冰上有 $K$ 个叉（$2 \le K \le 20000$）时，他比一头暴怒的公牛还要生气。

作为一名问题解决者，奥勒想出了一个计划来解决这个灾难性的局面。他打算把所有的叉都变成圆。冰场可以表示为一个 $N \times M$ 的网格，其中 $K$ 个方格有叉，其余 $N \cdot M - K$ 个方格为空。网格的行从上到下编号为 $0$ 到 $N-1$，列从左到右编号为 $0$ 到 $M-1$。当奥勒完成时，所有最初有叉的方格都应该变成圆。

最初，他在标有 S 的方格处。这个方格也包含一个叉。在一次移动中，他可以开始向上、向下、向右或向左四个方向之一移动，不能转弯。他将沿同一方向继续移动，直到到达一个叉或圆并停在该方格上。如果奥勒移动的方向上没有叉或圆，他将撞到墙壁，受到足以迫使他放弃计划的严重伤害。每次他到达一个叉，他都会完全停下来，并将其从叉变为圆。如果他到达一个圆，他也会完全停下来，并在盛怒之下将其变回叉。由于他时间有限，他想找到一个最多包含 $10^5$ 次移动的序列，将所有叉都变成圆。

为了额外的风格分，他还希望在开始的同一个方格结束，但并非所有子任务都要求做到这一点。

输入格式

输入的第一行包含三个整数 $N, M$ 和 $R$（$2 \le N \cdot M \le 10^6$, $R \in \{0,1\}$）。$N$ 和 $M$ 的值表示构成网格的行数和列数，$R$ 表示你是否必须返回起始方格。如果 $R=1$，你必须返回起始位置；如果 $R=0$，你可以在任何方格结束移动序列。

接下来 $N$ 行，每行包含一个长度为 $M$ 的字符串，其中第 $i$ 行（$i=0,1,\dots,N-1$）描述了冰场第 $i$ 行的样子。每个字符是 .、S 或 X 之一。保证只有一个方格包含 S，并且 X 的数量等于 $K-1$（因为起始方格也是一个叉）。

输出格式

如果存在一个将所有叉转换为圆的移动序列，首先输出该序列的长度。长度最多为 $10^5$。

在下一行，输出该序列。它应该由字符 v、<、^ 和 > 组成。v 表示奥勒向下移动，^ 向上移动，< 向左移动，> 向右移动。如果 $R=1$，奥勒还必须在开始的同一个方格结束。

如果没有有效的移动序列，则输出 -1，不再输出其他内容。请注意，有效序列的存在可能取决于 $R=0$ 还是 $R=1$。

3 3 0
S.X
...
X.X

8
>v^<><v^

2 2 0
S.
.X

-1

2 2 0
SX
X.

3
><v

2 2 1
SX
X.

-1

提示

样例解释

样例 $1$ 解释

最初，奥勒位于左上角的叉号处，网格如下所示：

X.X
...
X.X

在执行了移动 >、v 和 ^ 之后，奥勒位于网格的右上角单元格，网格如下所示：

X.X
...
X.O

在执行了移动 < 和 > 之后，他仍然位于网格的右上角单元格，网格如下所示：

O.O
...
X.O

最后，他将执行移动 <、v、^ 来创建一个没有叉号的冰场，并且他也会在起始位置结束（这不是此测试用例的要求，因为 $R = 0$）：

O.O
...
O.O

子任务

本题采用捆绑测试。 | 子任务编号 | 得分 | 限制 | |:-:|:-:|---| | $1$ |$20$ | $R = 0, K \le 100$ | | $2$ |$5$| $R = 0, K \le 5000$ | | $3$ |$15$ | $R = 0$ | | $4$ |$10$ | $R = 1, K \le 100$ | | $5$ |$30$ | $R = 1, K \le 10000$ | | $6$ |$20$ | $R = 1$ |