P13920 [PO Final 2024] 冰场之舞 / The Ice Puzzle

奥勒讨厌叉。它们让他想起在 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$。

### 样例解释 #### 样例 $1$ 解释 最初，奥勒位于左上角的叉号处，网格如下所示： ``` X.X ... X.X ``` 在执行了移动 >、v 和 ^ 之后，奥勒位于网格的右上角单元格，网格如下所示： ``` X.X ... X.O ``` 在执行了移动 < 和 > 之后，他仍然位于网格的右上角单元格，网格如下所示： ``` O.O ... X.O ``` 最后，他将执行移动