解题思路

设原字符串长度为 $n$，从 $(0,0)$ 出发，整段轨迹执行完后的最终坐标记为 $(sx,sy)$。

如果删除一段连续子串 $s[l+1 \dots r]$，那么：

• 删除前缀部分后，先走到前缀终点坐标；
• 删除的这一段不再执行；
• 后缀部分直接接到前缀后面继续走。

题目内容

多多正在检查一段配送轨迹日志。日志长度为$n$，从起点$(0,0)$出发，按顺序记录了每一步移动指令。日志是一个长度为$n$的字符串，只包含以下四种字符:

• U：向上移动一格;
• D：向下移动一格.
• R：向左移动一格.
• L：向右移动一格。

多多怀疑其中有一段连续日志被错误写入。现在他可以从原串中删除至多一段连续子串;删除后，剩余的前后两段会直接拼接，执行顺序保持不变。

这里的“至多一段”包含两种边界情况:

• 可以一个字符都不删;

• 也可以删掉整个字符串，此时剩余轨迹为空，最终仍停在$(0,0)$。

目标仓库坐标为$(x,y)$。请你求出最短需要删除多长的连续子串，才能让拼接后的整段轨迹最终停在$(x,y)$。

如果原始轨迹本来就停在$(x,y)$，可以不删除任何字符，此时答案为$0$。

如果不存在合法方案，输出$-1$。

输入描述

第一行输入一个整数$T$，表示测试数据组数。

接下来对每组数据:

• 第一行输入一个整数$n$，表示日志长度;
• 第二行输入一个长度恰好为$n$的字符串$s$;
• 第三行输入两个整数$x,y$，表示目标仓库坐标。

输出描述

对每组数据输出一个整数，表示最短删除长度。如果不存在合法方案，输出$-1$。

每组数据的答案各占一行。

补充说明

$1≤T≤3$

$1≤n≤10^6$

$S_i$只会是$U/D/L/R$

$-10^9≤x,y≤10^9$ 单个测试用例内所有测试数据的$n$之和不超过$10^6$

对于$30$的测试数据，保证单个测试用例内所有测试数据的$n$之和不超过$3000$

样例1

输入

2
6
RURDLD
0 0
3
UDL
2 0

输出

2
-1

说明

第一组数据中，删除第$3$到第$4$个字符$RD$后，剩余轨迹为$RULD$，其最终位移变为$(0,0)$。不存在长度为$1$的删除方案，因此答案为$2$。

第二组数据中，无论删除哪一段连续子串，剩余轨迹的最终位移都不可能变成$(2,0)$，因此答案为$-1$。