传送带

题目描述

我们有一个 $H$ 行 $W$ 列的网格。$(i,j)$ 表示从上数第 $i$ 行、从左数第 $j$ 列的格子。

格子 $(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}\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$。

样例

2 3
RDU
LRU

1 3

移动路径为 $(1,1) \to (1,2) \to (2,2) \to (2,3) \to (1,3)$，最终停在这里，所以答案为 $(1,3)$。

2 3
RRD
ULL

-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$。

9 44
RRDDDDRRRDDDRRRRRRDDDRDDDDRDDRDDDDDDRRDRRRRR
RRRDLRDRDLLLLRDRRLLLDDRDLLLRDDDLLLDRRLLLLLDD
DRDLRLDRDLRDRLDRLRDDLDDLRDRLDRLDDRLRRLRRRDRR
DDLRRDLDDLDDRLDDLDRDDRDDDDRLRRLRDDRRRLDRDRDD
RDLRRDLRDLLLLRRDLRDRRDRRRDLRDDLLLLDDDLLLLRDR
RDLLLLLRDLRDRLDDLDDRDRRDRLDRRRLDDDLDDDRDDLDR
RDLRRDLDDLRDRLRDLDDDLDDRLDRDRDLDRDLDDLRRDLRR
RDLDRRLDRLLLLDRDRLLLRDDLLLLLRDRLLLRRRRLLLDDR
RRRRDRDDRRRDDRDDDRRRDRDRDRDRRRRRRDDDRDDDDRRR

9 5

数据范围

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