题目描述

在一个由 H 行 W 列组成的古老迷宫中，冒险家 $Lily$ 站在入口（第1行第1列）准备开始他的探险之旅。迷宫中的每个格子都有一个神秘符号，这些符号代表着通往相邻格子的线索。

每个格子 (i, j) 上都有一个符号 $G_{i,j}$，它可以是“U”、“D”、“L”或“R”。

• “U” 表示如果 $Lily$ 不在第1行，他可以向上移动到 (i-1, j)。
• “D” 表示如果 $Lily$ 不在第 H 行，他可以向下移动到 (i+1, j)。
• “L” 表示如果 $Lily$ 不在第1列，他可以向左移动到 (i, j-1)。
• “R” 表示如果 $Lily$ 不在第 W 列，他可以向右移动到 (i, j+1)。

$Lily$ 按照这些线索不断移动，直到他无法再移动为止。

如果 $Lily$ 在移动过程中发现自己陷入了循环（即他又重新回到了之前已经走过的某个格子，并且后续的移动会让他重复之前的路径），他意识到必须停止并报告这一情况。

​任务​：

• 如果 $Lily$ 最终在某个格子 (i, j) 无法再移动，请输出这个格子的坐标。
• 如果 $Lily$ 发现自己陷入了无限循环，请输出 -1。

输入格式

输入的第一行包含两个整数 H 和 W，表示迷宫的行数和列数。 $(1 \leq H, W \leq 500)$

接下来的 H 行，每行包含 W 个字符，表示迷宫中每个格子的符号。

输出格式

• 如果 $Lily$ 在某个格子 (i, j) 停止移动，请输出 i j。
• 如果 $Lily$ 陷入无限循环，请输出 -1。

2 3
RDU
LRU

1 3

样例1解释：

将以 $(1, 1) \to (1, 2) \to (2, 2) \to (2, 3) \to (1, 3)$ 移动，在此处结束，因此答案是 $(1, 3)$ 。

2 3
RRD
ULL

-1

样例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”。

9 44
RRDDDDRRRDDDRRRRRRDDDRDDDDRDDRDDDDDDRRDRRRRR
RRRDLRDRDLLLLRDRRLLLDDRDLLLRDDDLLLDRRLLLLLDD
DRDLRLDRDLRDRLDRLRDDLDDLRDRLDRLDDRLRRLRRRDRR
DDLRRDLDDLDDRLDDLDRDDRDDDDRLRRLRDDRRRLDRDRDD
RDLRRDLRDLLLLRRDLRDRRDRRRDLRDDLLLLDDDLLLLRDR
RDLLLLLRDLRDRLDDLDDRDRRDRLDRRRLDDDLDDDRDDLDR
RDLRRDLDDLRDRLRDLDDDLDDRLDRDRDLDRDLDDLRRDLRR
RDLDRRLDRLLLLDRDRLLLRDDLLLLLRDRLLLRRRRLLLDDR
RRRRDRDDRRRDDRDDDRRRDRDRDRDRRRRRRDDDRDDDDRRR

9 5