问题描述

我们有一个 $H$ 行 $W$ 列的网格。$(i, j)$ 表示从上往下数第 $i$ 行，从左往右数第 $j$ 列的方块。
$(i,j)$ 上有一个字符 $G_{i,j}$。$G_{i,j}$ 的值可以是 U、D、L 或 R。

你最初位于 $(1,1)$。你执行以下操作，直到无法移动为止。

设 $(i,j)$ 是当前所在的方块。
如果 $G_{i,j}$ 为 U 且 $i \neq 1$，则移动到 $(i-1,j)$。
如果 $G_{i,j}$ 为 D 且 $i \neq H$，则移动到 $(i+1,j)$。
如果 $G_{i,j}$ 为 L 且 $j \neq 1$，则移动到 $(i,j-1)$。
如果 $G_{i,j}$ 为 R 且 $j \neq W$，则移动到 $(i,j+1)$。
否则，无法移动。

打印出你无法移动时所在的方块。
如果你无限循环移动，则打印 -1。

约束条件

• $1 \leq H, W \leq 500$
• $G_{i,j}$ 的值可以是 U、D、L 或 R。
• $H$ 和 $W$ 是整数。

输入

输入以以下格式从标准输入给出：

$H$ $W$ $G_{1,1}G_{1,2}\dots G_{1,W}$ $G_{2,1}G_{2,2}\dots G_{2,W}$ $\vdots$ $G_{H,1}G_{H,2}\dots G_{H,W}$

输出

如果你位于 $(i, j)$，请按以下格式打印：

$i$ $j$

如果你无限循环移动，请打印 -1。

示例 1

2 3
RDU
LRU

示例输出 1

1 3

你将会按照 $(1, 1) \to (1, 2) \to (2, 2) \to (2, 3) \to (1, 3)$ 移动，最后到达此处，因此答案是 $(1, 3)$。

示例 2

2 3
RRD
ULL

示例输出 2

-1

你将会无限循环地按照 $(1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (2, 2) \to (2, 1) \to (1, 1) \to (1, 2) \to \dots$ 移动，因此在这种情况下应该打印 -1。

示例 3

9 44
RRDDDDRRRDDDRRRRRRDDDRDDDDRDDRDDDDDDRRDRRRRR
RRRDLRDRDLLLLRDRRLLLDDRDLLLRDDDLLLDRRLLLLLDD
DRDLRLDRDLRDRLDRLRDDLDDLRDRLDRLDDRLRRLRRRDRR
DDLRRDLDDLDDRLDDLDRDDRDDDDRLRRLRDDRRRLDRDRDD
RDLRRDLRDLLLLRRDLRDRRDRRRDLRDDLLLLDDDLLLLRDR
RDLLLLLRDLRDRLDDLDDRDRRDRLDRRRLDDDLDDDRDDLDR
RDLRRDLDDLRDRLRDLDDDLDDRLDRDRDLDRDLDDLRRDLRR
RDLDRRLDRLLLLDRDRLLLRDDLLLLLRDRLLLRRRRLLLDDR
RRRRDRDDRRRDDRDDDRRRDRDRDRDRRRRRRDDDRDDDDRRR

示例输出 3

9 5