C-小红的机器人构造 - Ⅰ+Ⅱ+Ⅲ

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

$~~~~~~$ 在无限大的网格平面上，我们使用 $(x,y)$ 表示网格中第 $x$ 行第 $y$ 列的单元格。
$~~~~~~$ 小红有一只笨笨机器人初始位于 $(0,0)$ 单元格，她会向机器人下达 $n$ 个指令，机器人跟随指令上下左右移动。指令字符串由 $\texttt{U,D,L,R}$ 四个字符混合构成，以 $1$ 作为初始下标，形式化写作 $s_1s_2 \cdots s_n$ 。具体的，假设 $t$ 时刻机器人位于 $(i,j)$ 单元格，若指令字符串的第 $t+1$ 个字符存在：
$~~~~~~~~~$ $\bullet\$ 若 $s_{t+1} = \tt U$ ，则第 $t+1$ 时刻机器人位于 $(i + 1, j)$ ；
$~~~~~~~~~$ $\bullet\$ 若 $s_{t+1} = \tt D$ ，则第 $t+1$ 时刻机器人位于 $(i - 1, j)$ ；
$~~~~~~~~~$ $\bullet\$ 若 $s_{t+1} = \tt L$ ，则第 $t+1$ 时刻机器人位于 $(i, j - 1)$ ；
$~~~~~~~~~$ $\bullet\$ 若 $s_{t+1} = \tt R$ ，则第 $t+1$ 时刻机器人位于 $(i, j + 1)$ ；

$~~~~~~$ 给出指令字符串，询问，能否删除部分指令（保持其余指令的相对位置不变），使得机器人最终位于 $(x,y)$ 。如果可以，计算有多少种不同的删除方案（删除不同下标视为不同方案），并输出其中任意一种。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行输入三个整数  代表指令数量、终点位置。
第二行输入一个长度为  、仅由  四个字符混合构成的字符串  ，代表小红的指令字符串。

输出描述:

对于子问题Ⅰ，输出规范如下，你至多可以从中获取  分：
对于每一组测试数据，如果能够通过删除部分指令使得机器人最终位于终点  ，输出  。
否则，直接输出  。

对于子问题Ⅱ，输出规范如下，你至多可以从中获取  分：
对于每一组测试数据，如果能够通过删除部分指令使得机器人最终位于终点  ，在一行上输出  ，随后在同一行输出一个字符串，代表删除后的新指令串。彼此间使用单个空格间隔。
否则，直接输出  。

对于子问题Ⅲ，输出规范如下，你至多可以从中获取  分：
对于每一组测试数据，如果能够通过删除部分指令使得机器人最终位于终点  ，在一行上输出  ，随后在同一行输出一个字符串，代表删除后的新指令串；最后在同一行输出一个整数，代表符合条件的不同删除方案的数量，由于答案可能很大，请将答案对  取模后输出。彼此间使用单个空格间隔。
否则，直接输出  。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
本题采用类捆绑测试的  检查答案，通过空格分隔输出并依次检查答案，请你严格依照输出描述进行输出，输出多余内容、未按照子问题输出格式输出等行为，有可能会导致输出格式错误。如果你有任何疑问，欢迎在提问区向我们提出。

示例1

输入

复制

3
4 2 2
LRDU
4 0 0
LRDU
6 2 -3
LLULLU

输出

复制

NO
YES  4
YES LULLU 4

说明

对于第一个样例，无论怎么删除，机器人都无法到达到达终点。
对于第二个样例，将指令串全部删除是其中一种方案，与此同时， 、 和  也是合法的方案，所以一共有  种合法方案。
对于第三个样例，我们使用下划线  来填充被删除的位置，合法方案有： 、 、 和  。