TX202612 机器人指令修复

题目描述

机器人最初位于无限大的平面直角坐标系原点 (0, 0)。

机器人有四种移动指令：

每条指令都必须执行，不能停留在原地。

现在有一段长度为 N 的指令串，其中部分指令损坏，损坏的位置用 ? 表示。

你需要把每个 ? 替换为 D、L、R、U 中的一个，使机器人执行完全部指令后，恰好到达目标位置 (X, Y)。

已经确定的指令不能修改，也不能添加或删除指令。机器人途中可以重复经过同一个位置，平面上没有障碍物。

如果存在多种修复方案，请输出字典序最小的完整指令串。如果不存在，输出 -1。

本题规定字符顺序为：

D < L < R < U

输入格式

第一行包含一个正整数 N 和两个整数 X、Y，分别表示指令串长度和目标位置。

第二行包含一个长度为 N 的字符串 S，只包含 D、L、R、U、?。

输出格式

如果存在修复方案，输出字典序最小的完整指令串。

否则输出 -1。

样例 1 输入

4 0 0
?R??

样例 1 输出

DRLU

样例 1 说明

机器人依次经过：

(0, 0)
→ (0, -1)
→ (1, -1)
→ (0, -1)
→ (0, 0)

最终到达目标位置。

DRLU 是所有合法修复方案中字典序最小的指令串。

样例 2 输入

3 0 0
???

样例 2 输出

-1

样例 2 说明

无法用恰好三次规定的移动从原点出发并回到原点。

数据范围

• 1 ≤ N ≤ 2 × 10^5
• -10^9 ≤ X, Y ≤ 10^9
• S 的长度为 N
• S 只包含 D、L、R、U、?

子任务如下，各子任务独立计分：