坐标平面上有一个机器人。最初,机器人位于点$$$(0, 0)$$$。它的路径被描述为长度为$$$n$$$的字符串$$$s$$$,由字符'L'、'R'、'U'、'D'组成。
这些字符中的每一个都对应于一些动作:
- 'L'(左):表示机器人从点 $$$(x, y)$$$ 移动到点 $$$(x - 1, y)$$$;
- 'R'(右):表示机器人从点 $$$(x, y)$$$ 移动到点 $$$(x + 1, y)$$$;
- 'U'(向上):表示机器人从点 $$$(x, y)$$$ 移动到点 $$$(x, y + 1)$$$;
- 'D'(向下):表示机器人从点 $$$(x, y)$$$ 移动到点 $$$(x, y - 1)$$$。
创建这个机器人的公司要求你以某种方式优化机器人的路径。为此,您可以删除路径的任何非空子字符串。但这家公司不希望客户注意到机器人行为的变化。这意味着,如果在优化之前机器人在点 $$$(x_e, y_e)$$$ 结束其路径,那么在优化之后(即从 $$$s$$$ 中删除某些单个子字符串)机器人也会在点 $$$(x_e, y_e)$$$ 结束其路径。
此优化是一个低预算项目,因此您需要删除尽可能短的非空子字符串来优化机器人的路径,使其路径的端点不会改变。您可能无法优化路径。另外,优化后目标路径可能是空字符串(即删除的子字符串是整个字符串 $$$s$$$)。
回想一下,$$$s$$$ 的子字符串是可以通过从前缀中删除一些字符(可能是零)和从后缀中删除一些字符(可能是零)从 $$$s$$$ 获得的字符串。例如,“LURLLR”的子串是“LU”、“LR”、“LURLLR”、“URL”,但不是“RR”和“UL”。
您必须回答 $$$t$$$ 独立测试用例。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
接下来的 $$$2t$$$ 行描述测试用例。每个测试用例都分两行给出。测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 机器人路径的长度。测试用例的第二行包含一个字符串 $$$s$$$,由 $$$n$$$ 字符“L”、“R”、“U”、“D”组成——机器人的路径。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$)。
输出
对于每个测试用例,在其上打印答案。如果无法删除机器人路径端点不变的非空子字符串,则打印 -1。否则,打印两个整数 $$$l$$$ 和 $$$r$$$,使得 $$$1 \le l \le r \le n$$$ — 您删除的子字符串的端点。 $$$r-l+1$$$ 值应尽可能小。如果有多个答案,请打印其中任何一个。
示例
输入 #1
4 4 LRUD 4 LURD 5 RRUDU 5 LLDDR
输出 #1
1 2 1 4 3 4 -1