Olle 讨厌叉号（X）。这让他想起了在瑞典信息学奥林匹克（Programmeringsolympiaden）中拿到 Wrong Answer 的经历。

当他到达 Vallhamra 冰球馆，看到冰面上放置了 $K$（$2 \le K \le 20000$）个叉号时，他比一头愤怒的公牛还要生气。

作为一名问题解决者，Olle 想出了一个解决这一灾难性局面的计划。他打算将所有的叉号都变成圆圈（O）。冰面可以表示为一个 $N \times M$ 的网格，其中 $K$ 个格子有叉号，其余的 $N \cdot M - K$ 个格子是空的。网格的行从上到下从 $0$ 到 $N - 1$ 编号，列从左到右从 $0$ 到 $M - 1$ 编号。当 Olle 完成后，所有原本有叉号的格子都应该被转化为圆圈。

起初，他位于标记为 S 的格子上。这个格子也包含一个叉号。在一步移动中，他可以开始向上、下、右、左四个方向之一移动，期间无法转向。他将沿着同一个方向继续移动，直到到达一个叉号或圆圈并在该格子上停下。如果 Olle 移动的方向上没有叉号或圆圈，他将会撞到墙上，受到严重的伤害，从而被迫放弃他的计划。每次他到达一个叉号时，他会完全停下，并将该格子从叉号变为圆圈。如果他到达了一个圆圈，他也会完全停下，并在极度愤怒中将其变回叉号。由于他没有一整天的时间，他希望找到一个包含最多 $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 表示 Olle 应该向下移动，^ 表示向上，< 表示向左，> 表示向右。如果 $R = 1$，Olle 还必须在开始的同一个格子结束。

如果不存在合法的移动序列，仅输出 -1。注意，是否存在合法序列可能取决于 $R = 0$ 还是 $R = 1$。

子任务

你的解法将在多个测试点组上进行测试。要获得某个组的分数，必须通过该组中的所有测试用例。

样例

输入样例 1

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

输出样例 1

8
>v^<><v^

输入样例 2

2 2 0
S.
.X

输出样例 2

-1

输入样例 3

2 2 0
SX
X.

输出样例 3

3
><v

输入样例 4

2 2 1
SX
X.

输出样例 4

-1

说明

样例 1 说明

起初，Olle 位于左上角的叉号上，网格如下所示：

X.X
...
X.X

在进行移动 >、v 和 ^ 之后，Olle 位于网格的右上角格子，网格如下所示：

X.X
...
X.O

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

O.O
...
X.O

最后，他将进行移动 <、v、^，从而创造一个没有叉号的冰面，并且他也在起点位置结束（在本测试用例中这不是必需的，因为 $R = 0$）：

O.O
...
O.O