K. 拯救猫猫
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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

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

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

  • 每一步只能移动到相邻的四个空格（上、下、左、右）之一

  • 不能跨越网格边界

  • 不能进入任何狗的视线范围内

  • 不能经过狗或障碍物所在的格子

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

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

Input

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

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

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

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

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

Output

对于每组测试数据：

如果不存在让库若猫逃脱的方案，输出用空格分隔的两个 $$$-1$$$ 。

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

Example
Input
3
7 7
.D....E
...#..L
..#...L
.#.L..D
....#..
#.L....
S...#.L
3 3
..E
R.L
S..
4 4
.D.E
....
.D..
S...
Output
1 2
-1 -1
1 2
Note

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