最近您购买了雪地行走机器人并带回家。假设您的家是无限网格上的一个单元格 $$$(0, 0)$$$。
您还拥有该机器人的指令序列。它被写为由字符“L”、“R”、“U”和“D”组成的字符串$$$s$$$。如果机器人现在位于单元格 $$$(x, y)$$$ 中,他可以移动到相邻单元格之一(取决于当前指令)。
- 如果当前指令是'L',则机器人可以向左移动到$$$(x - 1, y)$$$;
- 如果当前指令是'R',则机器人可以向右移动到$$$(x + 1, y)$$$;
- 如果当前指令是'U',则机器人可以移动到顶部$$$(x, y + 1)$$$;
- 如果当前指令是“D”,则机器人可以移动到底部$$$(x, y - 1)$$$。
您已经注意到手册最后一页上的警告:如果机器人访问某个单元格($$$(0, 0)$$$ 除外)两次,那么它就会崩溃。
因此,如果机器人从单元格 $$$(0, 0)$$$ 开始,执行给定的指令,访问除 $$$(0, 0)$$$ 以外的单元格两次或更多次,并在单元格 $$$(0, 0)$$$ 中结束路径,则指令序列有效。此外,单元格 $$$(0, 0)$$$ 最多应被访问两次:在开头和结尾(如果路径为空,则仅访问一次)。例如,以下指令序列被视为有效:“UD”、“RL”、“UUURULLDDDDLDDRRUU”,以下指令被视为无效:“U”(端点不是 $$$(0, 0)$$$)和“UUDD”(单元格 $$$(0, 1)$$$ 被访问两次)。
但是,初始指令序列可能无效。您不希望您的机器人损坏,因此您决定通过以下方式对其进行重新编程:您将从初始指令序列中删除一些(可能是全部或全部)指令,然后根据您的意愿重新排列剩余指令并打开您的机器人进行移动。
您的任务是从初始序列中删除尽可能少的指令,并重新排列剩余的指令以使序列有效。报告您可以获得的最大长度的有效序列。
请注意,您可以选择剩余指令的任意顺序(您不需要最小化交换次数或任何其他类似指标)。
您必须回答 $$$q$$$ 独立测试用例。
输入
输入的第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^4$$$) — 测试用例的数量。
接下来的 $$$q$$$ 行包含测试用例。第 $$$i$$$ 测试用例以字符串 $$$s$$$ 形式给出,该字符串至少包含 $$$1$$$ 且不超过 $$$10^5$$$ 个字符“L”、“R”、“U”和“D”——初始指令序列。
保证所有测试用例中 $$$|s|$$$ 的总和(其中 $$$|s|$$$ 是 $$$s$$$ 的长度)不超过 $$$10^5$$$ ($$$\sum |s| \le 10^5$$$)。
输出
对于每个测试用例,请在其上打印答案。在第一行中打印剩余指令的最大数量。在第二行中打印机器人必须执行的剩余指令 $$$t$$$ 的有效序列。移动按照打印顺序从左到右执行。如果有多个答案,您可以打印任何一个。如果答案是$$$0$$$,则允许打印空行(但可以不打印)。
示例
输入 #1
6 LRU DURLDRUDRULRDURDDL LRUDDLRUDRUL LLLLRRRR URDUR LLL
输出 #1
2 LR 14 RUURDDDDLLLUUR 12 ULDDDRRRUULL 2 LR 2 UD 0
注意
第一个测试用例中只有两个可能的答案:“LR”和“RL”。
第二个测试用例对应的图片:
请注意,移动方向并不重要
第三个测试用例的另一个正确答案:“URDDLLLUURDR”。