题目描述

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

样例输入 #1

2 3
RDU
LRU

样例输出 #1

1 3

样例 #2

样例输入 #2

2 3
RRD
ULL

样例输出 #2

-1

样例 #3

样例输入 #3

9 44
RRDDDDRRRDDDRRRRRRDDDRDDDDRDDRDDDDDDRRDRRRRR
RRRDLRDRDLLLLRDRRLLLDDRDLLLRDDDLLLDRRLLLLLDD
DRDLRLDRDLRDRLDRLRDDLDDLRDRLDRLDDRLRRLRRRDRR
DDLRRDLDDLDDRLDDLDRDDRDDDDRLRRLRDDRRRLDRDRDD
RDLRRDLRDLLLLRRDLRDRRDRRRDLRDDLLLLDDDLLLLRDR
RDLLLLLRDLRDRLDDLDDRDRRDRLDRRRLDDDLDDDRDDLDR
RDLRRDLDDLRDRLRDLDDDLDDRLDRDRDLDRDLDDLRRDLRR
RDLDRRLDRLLLLDRDRLLLRDDLLLLLRDRLLLRRRRLLLDDR
RRRRDRDDRRRDDRDDDRRRDRDRDRDRRRRRRDDDRDDDDRRR

样例输出 #3

9 5

提示

数据范围

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

样例说明 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 。