题目描述

给定一个 $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$ —— 分别表示网格的行数和列数。

接下来 $H$ 行，每行包含一个长度为 $W$ 的字符串。其中第 $i$ 行的第 $j$ 个字符表示 $G_{i,j}$。

输出格式

如果你最终停留在格子 $(i, j)$，请在一行中依次输出 $i$ 和 $j$，中间用一个空格隔开。

如果你会无限重复移动，请输出 -1。

样例输入 1

2 3
RDU
LRU

样例输出 1

1 3

样例输入 2

2 3
RRD
ULL

样例输出 2

-1

样例输入 3

9 44
RRDDDDRRRDDDRRRRRRDDDRDDDDRDDRDDDDDDRRDRRRRR
RRRDLRDRDLLLLRDRRLLLDDRDLLLRDDDLLLDRRLLLLLDD
DRDLRLDRDLRDRLDRLRDDLDDLRDRLDRLDDRLRRLRRRDRR
DDLRRDLDDLDDRLDDLDRDDRDDDDRLRRLRDDRRRLDRDRDD
RDLRRDLRDLLLLRRDLRDRRDRRRDLRDDLLLLDDDLLLLRDR
RDLLLLLRDLRDRLDDLDDRDRRDRLDRRRLDDDLDDDRDDLDR
RDLRRDLDDLRDRLRDLDDDLDDRLDRDRDLDRDLDDLRRDLRR
RDLDRRLDRLLLLDRDRLLLRDDLLLLLRDRLLLRRRRLLLDDR
RRRRDRDDRRRDDRDDDRRRDRDRDRDRRRRRRDDDRDDDDRRR

样例输出 3

9 5

说明

样例解释

• 在第一个样例中，你的移动路径为：$(1,1) \to (1,2) \to (2,2) \to (2,3) \to (1,3)$，然后无法继续移动。因此，最终停留的格子为 $(1,3)$。
• 在第二个样例中，你的移动路径为：$(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 \le H, W \le 500$。
• 保证 $G_{i,j}$ 均是 U, D, L, 或 R 之一。
• 保证所有的输入数值均为整数。