题目描述

给定一个矩阵 $g$，里面有许许多多的 LRUD 四个字母。

一个机器人从点 $(1,1)$ 出发，假设它到了点 $(x,y)$，则：

如果 $g_{x,y}$ 是 U，移动到 $(x-1,y)$。

如果 $g_{x,y}$ 是 D，移动到 $(x+1,y)$。

如果 $g_{x,y}$ 是 L，移动到 $(x,y-1)$。

如果 $g_{x,y}$ 是 R，移动到 $(x,y+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

提示

约束

对于 $10\%$ 的测试数据，$H=W=1$；

对于另外 $20\%$ 的测试数据，$\min(H,W)=1$；

对于另外 $10\%$ 的测试数据，所有 $G_{i,j}$ 相同；

对于 $100\%$ 的测试数据：

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

样例解释 1

你将移动到(1,1) → (1,2) → (2,2) → (2,3) → (1,3)，最终停留在这里，答案为(1,3)。

样例解释 2

你将无限循环地移动到(1,1) → (1,2) → (1,3) → (2,3) → (2,2) → (2,1) → (1,1) → (1,2) → …，因此输出-1。