该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

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

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

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

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

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

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

Format

Input

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

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

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

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

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

Output

对于每组测试数据：

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

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

Samples

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

Note

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