The robot is located on a checkered rectangular board of size n × m (n rows, m columns). The rows in the board are numbered from 1 to n from top to bottom, and the columns — from 1 to m from left to right.

The robot is able to move from the current cell to one of the four cells adjacent by side.

Each cell has one of the symbols 'L', 'R', 'D' or 'U' written on it, indicating the direction in which the robot will move when it gets in that cell — left, right, down or up, respectively.

The robot can start its movement in any cell. He then moves to the adjacent square in the direction indicated on the current square in one move. 

  * If the robot moves beyond the edge of the board, it falls and breaks. 
  * If the robot appears in the cell it already visited before, it breaks (it stops and doesn't move anymore). 



Robot can choose any cell as the starting cell. Its goal is to make the maximum number of steps before it breaks or stops.

Determine from which square the robot should start its movement in order to execute as many commands as possible. A command is considered successfully completed if the robot has moved from the square on which that command was written (it does not matter whether to another square or beyond the edge of the board).

Input

The first line contains an integer t (1 ≤ t ≤ 10000) — the number of test cases in the test.

Each test case's description is preceded by a blank line. Next is a line that contains integers n and m (1 ≤ n ≤ 2000; 1 ≤ m ≤ 2000) — the height and width of the board. This line followed by n lines, the i-th of which describes the i-th line of the board. Each of them is exactly m letters long and consists of symbols 'L', 'R', 'D' and 'U'.

It is guaranteed that the sum of sizes of all boards in the input does not exceed 4⋅10^6.

Output

For each test case, output three integers r, c and d (1 ≤ r ≤ n; 1 ≤ c ≤ m; d ≥ 0), which denote that the robot should start moving from cell (r, c) to make the maximum number of moves d. If there are several answers, output any of them.

Example

Input


7

1 1
R

1 3
RRL

2 2
DL
RU

2 2
UD
RU

3 2
DL
UL
RU

4 4
RRRD
RUUD
URUD
ULLR

4 4
DDLU
RDDU
UUUU
RDLD


Output


1 1 1
1 1 3
1 1 4
2 1 3
3 1 5
4 3 12
1 1 4

Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Implementation

Complete search

Dynamic programming
Skill types: Dynamic programming

Complete search

Starter code:

Solutions:
from sys import stdin
input = stdin.readline
moves = {'R': (0, 1), 'L': (0, -1), 'U': (-1, 0), 'D': (1, 0)}
lengths = []

def dumbdfs(x, y):
	global lengths
	path = []
	lenn = 0
	curx = x
	cury = y
	cycle = False
	cycle_start = 0
	while curx >= 0 and curx < n and (cury >= 0) and (cury < m):
		if lengths[curx][cury] == -1:
			cycle_start = path.index((curx, cury))
			cycle = True
			break
		if lengths[curx][cury] > 0:
			lenn += lengths[curx][cury]
			break
		lenn += 1
		lengths[curx][cury] = -1
		path.append((curx, cury))
		(dx, dy) = moves[field[curx][cury]]
		curx += dx
		cury += dy
	if cycle:
		for i in range(lenn, lenn - cycle_start, -1):
			lengths[path[lenn - i][0]][path[lenn - i][1]] = i
		for i in range(cycle_start, len(path)):
			lengths[path[i][0]][path[i][1]] = lenn - cycle_start
	else:
		for i in range(lenn, lenn - len(path), -1):
			lengths[path[lenn - i][0]][path[lenn - i][1]] = i
t = int(input())
for _ in range(t):
	input()
	(n, m) = map(int, input().split(' '))
	field = [input() for _ in range(n)]
	lengths = [[0 for _ in range(m)] for _ in range(n)]
	for x in range(n):
		for y in range(m):
			if not lengths[x][y]:
				dumbdfs(x, y)
	maxx = 0
	maxy = 0
	maxv = 0
	for x in range(n):
		for y in range(m):
			if lengths[x][y] > maxv:
				maxv = lengths[x][y]
				maxx = x + 1
				maxy = y + 1
	print(maxx, maxy, maxv)


def resolve(n, m, board):
	v = [[0] * m for _ in range(n)]
	idx = 0
	(mx, tr, tc) = (0, 0, 0)
	for r in range(n):
		for c in range(m):
			if v[r][c] > 0:
				continue
			idx -= 1
			(cr, cc) = (r, c)
			stk = []
			while 0 <= cr < n and 0 <= cc < m and (v[cr][cc] == 0):
				stk.append((cr, cc))
				v[cr][cc] = idx
				d = board[cr][cc]
				if d == 'L':
					cc -= 1
				elif d == 'R':
					cc += 1
				elif d == 'U':
					cr -= 1
				else:
					cr += 1
			cv = 0
			if 0 <= cr < n and 0 <= cc < m:
				if v[cr][cc] > 0:
					cv = v[cr][cc] + 1
				else:
					cv = len(stk)
					i = 0
					while stk[i] != (cr, cc):
						v[stk[i][0]][stk[i][1]] = cv
						i += 1
						cv -= 1
					for (ccr, ccc) in stk[i:]:
						v[ccr][ccc] = cv
					stk = []
			else:
				cv = 1
			for i in range(len(stk) - 1, -1, -1):
				v[stk[i][0]][stk[i][1]] = cv
				cv += 1
			if v[r][c] > mx:
				(mx, tr, tc) = (v[r][c], r, c)
	return f'{tr + 1} {tc + 1} {mx}'
t = int(input())
ans = []
for _ in range(t):
	input()
	(n, m) = [int(_) for _ in input().split()]
	board = [input() for _ in range(n)]
	ans.append(resolve(n, m, board))
print('\n'.join(ans))


from collections import deque
import sys
input = sys.stdin.readline

def f(x, y):
	return x * m + y

def g(x):
	return (x // m, x % m)

def bfs(nx, ny):
	u = []
	while not visit[nx][ny]:
		f0 = f(nx, ny)
		u.append(f0)
		visit[nx][ny] = len(u)
		(dx, dy) = d0[s[nx][ny]]
		nx += dx
		ny += dy
		if 0 <= nx < n and 0 <= ny < m and visit[nx][ny] and (dist[nx][ny] == -1):
			break
		if not 0 <= nx < n or not 0 <= ny < m or visit[nx][ny]:
			c = 1 if not 0 <= nx < n or not 0 <= ny < m else dist[nx][ny] + 1
			for i in range(len(u) - 1, -1, -1):
				(x, y) = g(u[i])
				dist[x][y] = c
				c += 1
			return
	c = len(u) - visit[nx][ny] + 1
	for i in range(visit[nx][ny] - 1, len(u)):
		(x, y) = g(u[i])
		dist[x][y] = c
	for i in range(visit[nx][ny] - 2, -1, -1):
		(x, y) = g(u[i])
		c += 1
		dist[x][y] = c
	return
t = int(input())
d0 = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
ans = []
for _ in range(t):
	input()
	(n, m) = map(int, input().split())
	s = [list(input().rstrip()) for _ in range(n)]
	visit = [[0] * m for _ in range(n)]
	dist = [[-1] * m for _ in range(n)]
	for i in range(n):
		for j in range(m):
			if not visit[i][j]:
				bfs(i, j)
	(r, c, d) = (-1, -1, 0)
	for i in range(n):
		di = dist[i]
		for j in range(m):
			if d < di[j]:
				(r, c, d) = (i + 1, j + 1, di[j])
	ans.append(' '.join(map(str, [r, c, d])))
sys.stdout.write('\n'.join(ans))


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main(t):
	s = input()
	(m, n) = map(int, input().split())
	grid = []
	for i in range(m):
		grid.append(input())
	nextindex = [-1] * (m * n)
	away = [0] * (m * n + 1)
	direc = {ord('U'): [-1, 0], ord('D'): [1, 0], ord('L'): [0, -1], ord('R'): [0, 1]}
	visited = [False] * (m * n)
	indegree = [0] * (m * n)
	for i in range(m):
		for j in range(n):
			index = i * n + j
			newi = i + direc[grid[i][j]][0]
			newj = j + direc[grid[i][j]][1]
			if newi < 0 or newi >= m or newj < 0 or (newj >= n):
				continue
			nextindex[index] = newi * n + newj
			indegree[newi * n + newj] += 1
	for index in range(m * n):
		if indegree[index] > 0:
			continue
		seq = []
		while not visited[index] and index != -1 and (away[index] == 0):
			seq.append(index)
			visited[index] = True
			index = nextindex[index]
		if index < 0:
			for (i, ind) in enumerate(seq):
				away[ind] = len(seq) - i
		else:
			base = away[index]
			flag = False
			loop = len(seq)
			for (i, ind) in enumerate(seq):
				if ind == index:
					flag = True
				if not flag:
					loop -= 1
				away[ind] = max(len(seq) - i, loop) + base
	for index in range(m * n):
		if away[index] > 0:
			continue
		loop = 0
		seq = []
		while not visited[index]:
			seq.append(index)
			visited[index] = True
			index = nextindex[index]
			loop += 1
		for num in seq:
			away[num] = loop
	maximum = max(away)
	for i in range(m * n):
		if away[i] == maximum:
			print(i // n + 1, i % n + 1, away[i])
			return
T = int(input())
t = 1
while t <= T:
	main(t)
	t += 1


import sys, collections, math, bisect, heapq, random, functools
input = sys.stdin.readline
out = sys.stdout.flush

def solve():
	blank = input()
	(n, m) = map(int, input().split())
	matrix = [list(input().rstrip('\n')) for i in range(n)]
	dir_ = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
	(maxv, x, y) = (0, 0, 0)
	dis = [[0 for i in range(m)] for i in range(n)]

	def bfs(x, y):
		nonlocal dis, dir_, matrix
		path = []
		is_loop = False
		loop_head = 0
		(cx, cy) = (x, y)
		d = 0
		while 0 <= cx < n and 0 <= cy < m:
			if dis[cx][cy] == -1:
				loop_head = path.index(cx * m + cy)
				is_loop = True
				break
			if dis[cx][cy] > 0:
				d += dis[cx][cy]
				break
			d += 1
			dis[cx][cy] = -1
			path.append(cx * m + cy)
			(dx, dy) = dir_[matrix[cx][cy]]
			cx += dx
			cy += dy
		if is_loop:
			for i in range(0, loop_head):
				dis[path[i] // m][path[i] % m] = d - i
			for i in range(loop_head, len(path)):
				dis[path[i] // m][path[i] % m] = d - loop_head
		else:
			for i in range(len(path)):
				dis[path[i] // m][path[i] % m] = d - i
	for i in range(n):
		for j in range(m):
			bfs(i, j)
	for i in range(n):
		for j in range(m):
			if dis[i][j] > maxv:
				maxv = dis[i][j]
				(x, y) = (i, j)
	print(x + 1, y + 1, maxv)
for i in range(int(input())):
	solve()


import sys
for _ in range(int(sys.stdin.readline())):
	sys.stdin.readline()
	(n, m) = [int(_) for _ in sys.stdin.readline().split()]
	d = [[-1 if j == 'R' else -2 if j == 'U' else -3 if j == 'L' else -4 for j in sys.stdin.readline().strip()] for i in range(n)]
	r = 0
	pos = (0, 0)
	for i in range(n):
		for j in range(m):
			(a, b, p, c, st) = (i, j, d[i][j], 0, [])
			while p < 0:
				d[a][b] = 0
				st.append((a, b))
				if p == -1:
					b += 1
				elif p == -2:
					a -= 1
				elif p == -3:
					b -= 1
				else:
					a += 1
				c += 1
				if 0 <= a < n and 0 <= b < m:
					p = d[a][b]
				else:
					for (ii, (x, y)) in enumerate(st):
						d[x][y] = c - ii
					p = -1
					break
			if p == 0:
				jj = flag = 0
				for (ii, (x, y)) in enumerate(st):
					d[x][y] = c - jj if flag else c - ii
					if x == a and y == b:
						flag = 1
						jj = ii
			if p > 0:
				for (ii, (x, y)) in enumerate(st):
					d[x][y] = p + c - ii
			if d[i][j] > r:
				r = d[i][j]
				pos = (i, j)
	print(pos[0] + 1, pos[1] + 1, r)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def robotOnTheBoard2():
	input()
	(n, m) = inlt()
	board = []
	for i in range(n):
		board.append(insr())
	nxt_index = [-1] * (m * n)
	in_degree = [0] * (m * n)
	visited = [False] * (m * n)
	values = [0] * (m * n)
	for i in range(n):
		for j in range(m):
			index = i * m + j
			nxt_i = i
			nxt_j = j
			if board[i][j] == 'L':
				nxt_j -= 1
			elif board[i][j] == 'R':
				nxt_j += 1
			elif board[i][j] == 'U':
				nxt_i -= 1
			elif board[i][j] == 'D':
				nxt_i += 1
			if nxt_i < 0 or nxt_i >= n or nxt_j < 0 or (nxt_j >= m):
				continue
			nxt_index[index] = nxt_i * m + nxt_j
			in_degree[nxt_i * m + nxt_j] += 1
	for index in range(m * n):
		if in_degree[index] != 0:
			continue
		seq = []
		while not visited[index] and index != -1:
			seq.append(index)
			visited[index] = True
			index = nxt_index[index]
		if index == -1:
			for (i, idx) in enumerate(seq):
				values[idx] = len(seq) - i
		else:
			base = values[index]
			loop_flag = False
			loop_length = len(seq)
			for (i, idx) in enumerate(seq):
				if idx == index:
					loop_flag = True
				if loop_flag is False:
					loop_length -= 1
				values[idx] = max(len(seq) - i, loop_length) + base
	for index in range(m * n):
		if values[index] > 0:
			continue
		loop_length = 0
		seq = []
		while not visited[index]:
			seq.append(index)
			visited[index] = True
			index = nxt_index[index]
			loop_length += 1
		for idx in seq:
			values[idx] = loop_length
	maximum = max(values)
	for i in range(m * n):
		if values[i] == maximum:
			print(i // m + 1, i % m + 1, values[i])
			return
t = inp()
for i in range(t):
	robotOnTheBoard2()


import sys

def solve():
	_ = sys.stdin.readline()
	(n, m) = map(int, sys.stdin.readline().split())
	s = [list(sys.stdin.readline()[:-1]) for _ in range(n)]
	dic = {'L': (0, -1), 'R': (0, 1), 'D': (1, 0), 'U': (-1, 0)}
	ans = [1, 1, 0]
	for i in range(n):
		for j in range(m):
			if isinstance(s[i][j], str):
				(x, y) = (i, j)
				path = []
				while 0 <= x < n and 0 <= y < m and isinstance(s[x][y], str):
					path.append(x)
					path.append(y)
					(dx, dy) = dic[s[x][y]]
					s[x][y] = -1
					x = x + dx
					y = y + dy
				if 0 <= x < n and 0 <= y < m and (s[x][y] == -1):
					steps = 1
					ind = len(path) - 2
					while ind > 0 and (not (path[ind] == x and path[ind + 1] == y)):
						steps += 1
						ind -= 2
					for z in range(ind, len(path), 2):
						(nx, ny) = (path[z], path[z + 1])
						s[nx][ny] = steps
					while len(path) > ind:
						path.pop()
				steps = 0
				if 0 <= x < n and 0 <= y < m:
					steps = s[x][y]
				while len(path) > 0:
					steps += 1
					y = path.pop()
					x = path.pop()
					s[x][y] = steps
				if steps > ans[2]:
					ans[0] = x + 1
					ans[1] = y + 1
					ans[2] = steps
	print(*ans)
for t in range(int(input())):
	solve()


import os, sys
input = lambda : sys.stdin.buffer.readline().rstrip(b'\r\n')

def dbp(*args, **kwargs):
	print(*args, file=sys.stderr, **kwargs)
a_str = lambda : input().decode('ascii')
get_int_list = lambda : [int(x) for x in input().split()]
join_str = lambda l, ch=' ': ch.join((str(x) for x in l))

def do_thing():
	input()
	(R, C) = get_int_list()
	dd = {'L': -1, 'U': -2, 'R': -3, 'D': -4}
	g = [[0] * (C + 2)] + [[0] + [dd[ch] for ch in a_str()] + [0] for _ in range(R)] + [[0] * (C + 2)]
	dr = {-1: 0, -2: -1, -3: 0, -4: 1}
	dc = {-1: -1, -2: 0, -3: 1, -4: 0}
	maxpath = float('-inf')
	best = []
	for sr in range(1, R + 1):
		for sc in range(1, C + 1):
			(r, c) = (sr, sc)
			dv = g[r][c]
			if dv >= 0:
				continue
			path = []
			upstep = -5
			while -5 < g[r][c] < 0:
				path.append((r, c))
				g[r][c] = upstep
				upstep -= 1
				r += dr[dv]
				c += dc[dv]
				dv = g[r][c]
			if dv < -4:
				cyclelength = dv - upstep
				while g[r][c] <= dv:
					g[r][c] = cyclelength
					(r, c) = path.pop()
			step = g[r][c]
			for (r, c) in reversed(path):
				step += 1
				g[r][c] = step
			if step == maxpath:
				best.append((r, c))
			elif step > maxpath:
				maxpath = step
				best = [(r, c)]
	return join_str((best[0][0], best[0][1], maxpath))
maxcc = 1
maxcc = int(input())
for cc in range(maxcc):
	print(do_thing())