题目描述

有一个 $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。

输入格式

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

$H$ $W$

$G_{1,1}$ $G_{1,2}$ $\cdots$ $G_{1,W}$

$G_{2,1}$ $G_{2,2}$ $\cdots$ $G_{2,W}$

$\vdots$

$G_{H,1}$ $G_{H,2}$ $\cdots$ $G_{H,W}$

输出格式

如果你最终停在 $(i,j)$，按以下格式输出：
$i$ $j$
如果你无限循环移动，输出 -1。

样例

2 3
RDU
LRU

1 3

2 3
RRD
ULL

-1

9 44
RRDDDDRRRDDDRRRRRRDDDRDDDDRDDRDDDDDDRRDRRRRR
RRRDLRDRDLLLLRDRRLLLDDRDLLLRDDDLLLDRRLLLLLDD
DRDLRLDRDLRDRLDRLRDDLDDLRDRLDRLDDRLRRLRRRDRR
DDLRRDLDDLDDRLDDLDRDDRDDDDRLRRLRDDRRRLDRDRDD
RDLRRDLRDLLLLRRDLRDRRDRRRDLRDDLLLLDDDLLLLRDR

9 5

样例解释

【样例1说明】
你将按 $(1, 1) \to (1, 2) \to (2, 2) \to (2, 3) \to (1, 3)$ 移动，最终停在这里，所以答案是 $(1, 3)$。
【样例2说明】
你将无限循环移动 $(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。

数据范围

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

来源

• AtCoder ABC265C