P9626 [ICPC 2020 Nanjing R] Evil Coordinate

一个机器人站在一个无限的二维平面上。它被编程为一个长度为 $n$ 的字符串 $s_1s_2\cdots s_n$，其中 $s_i \in \{\text{`U'}, \text{`D'}, \text{`L'}, \text{`R'}\}$，机器人将从 $(0, 0)$ 开始移动，并按照字符串中的字符指令进行移动。 更正式地说，设 $(x, y)$ 为机器人的当前位置。机器人从 $(0, 0)$ 开始，重复以下过程 $n$ 次。在第 $i$ 次时： - 如果 $s_i = \text{U}$，机器人从 $(x, y)$ 移动到 $(x, y+1)$； - 如果 $s_i = \text{D}$，机器人从 $(x, y)$ 移动到 $(x, y-1)$； - 如果 $s_i = \text{L}$，机器人从 $(x, y)$ 移动到 $(x-1, y)$； - 如果 $s_i = \text{R}$，机器人从 $(x, y)$ 移动到 $(x+1, y)$。 然而，在坐标 $(m_x, m_y)$ 下埋有一个地雷。如果机器人在移动过程中踩到 $(m_x, m_y)$，它将被炸成碎片。可怜的机器人！ 你的任务是重新排列字符串中的字符，使得机器人不会踩到 $(m_x, m_y)$。

有多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例： 第一行包含两个整数 $m_x$ 和 $m_y$ ($-10^9 \le m_x, m_y \le 10^9$)，表示地雷的坐标。 第二行包含一个字符串 $s_1s_2\cdots s_n$，长度为 $n$ ($1 \le n \le 10^5$, $s_i \in \{\text{`U'}, \text{`D'}, \text{`L'}, \text{`R'}\}$)，表示编程到机器人中的字符串。 保证所有测试用例的 $n$ 的总和不超过 $10^6$。

对于每个测试用例输出一行。如果存在有效答案，打印重新排列后的字符串，否则打印 "Impossible"。如果有多个有效答案，可以打印其中任意一个。

题面翻译由 ChatGPT-4o 提供。