题目描述

库若猫误入了狗群守护的街区，他需要你的帮助！

街区是一个 $n \times m (1 \leq n, m \leq 2000)$ 的网格。每个格子可能是空地、障碍物或狗。每只狗朝向固定的方向（上、下、左或右），它的视线会沿其正前方延伸，直到被障碍物或另一只狗阻挡。

库若猫被困在起点 $S$，必须从街区出口 $E$ 逃脱，他的移动遵循以下规则：

• 每一步只能移动到相邻的四个空格（上、下、左、右）之一
• 不能跨越网格边界
• 不能进入任何狗的视线范围内
• 不能经过狗或障碍物所在的格子

你可以让一只狗睡着。睡着的狗会失去视线，但库若猫仍然不能经过它。请判断是否存在一种方案，使得库若猫能够顺利到达出口：如果存在，找出这只狗的坐标。

保证网格中至少存在一只狗，起点 $S$ 和出口 $E$ 是空地且不在任何狗的视线内。

输入格式

每个测试文件包含多组测试数据。输入的第一行包含一个整数 $t$ ( $1 \leq t \leq 100$ ) 表示测试数据的数量。

每个测试数据的第一行包含两个整数 n 和 m ( $1 \leq n, m \leq 2000$ )，表示网格的行数和列数。

接下来的 $n$ 行，每行包含一个长度为$m$ 的字符串，表示街区的布局：

• . 表示空地
• # 表示障碍物
• E 表示街区出口
• S 表示库若猫的起点
• U、D、L、R 表示朝向分别为上，下，左，右的狗

保证所有测试数据中 $n$ 和 $m$ 的总和均不超过 2000。

输出格式

对于每组测试数据：

• 如果不存在让库若猫逃脱的方案，输出用空格分隔的两个 -1。
• 否则，输出用空格分隔的整数 $x$ 和 $y$ ( $1 \leq x \leq n, 1 \leq y \leq m$ )，表示被选定睡着的狗的行坐标和列坐标。如果存在多种方案，优先选择行坐标 $x$ 最小的方案；若行坐标相同，优先选择列坐标 $y$ 最小的方案。

3
7 7
.D....E
...#..L
..#...L
.#.L..D
....#..
#.L....
S...#.L
3 3
..E
R.L
S..
4 4
.D.E
....
.D..
S...

1 2
-1 -1
1 2

解释 #1

网格的行从上到下编号为 $1$ 到 $n$ ，列从左到右编号为 $1$ 到 $m$ 。