#P9626. [ICPC 2020 Nanjing R] Evil Coordinate

[ICPC 2020 Nanjing R] Evil Coordinate

Description

一个机器人站在一个无限的二维平面上。它被编程为一个长度为 nn 的字符串 s1s2sns_1s_2\cdots s_n,其中 $s_i \in \{\text{`U'}, \text{`D'}, \text{`L'}, \text{`R'}\}$,机器人将从 (0,0)(0, 0) 开始移动,并按照字符串中的字符指令进行移动。

更正式地说,设 (x,y)(x, y) 为机器人的当前位置。机器人从 (0,0)(0, 0) 开始,重复以下过程 nn 次。在第 ii 次时:

  • 如果 si=Us_i = \text{U},机器人从 (x,y)(x, y) 移动到 (x,y+1)(x, y+1)
  • 如果 si=Ds_i = \text{D},机器人从 (x,y)(x, y) 移动到 (x,y1)(x, y-1)
  • 如果 si=Ls_i = \text{L},机器人从 (x,y)(x, y) 移动到 (x1,y)(x-1, y)
  • 如果 si=Rs_i = \text{R},机器人从 (x,y)(x, y) 移动到 (x+1,y)(x+1, y)

然而,在坐标 (mx,my)(m_x, m_y) 下埋有一个地雷。如果机器人在移动过程中踩到 (mx,my)(m_x, m_y),它将被炸成碎片。可怜的机器人!

你的任务是重新排列字符串中的字符,使得机器人不会踩到 (mx,my)(m_x, m_y)

Input Format

有多个测试用例。输入的第一行包含一个整数 TT,表示测试用例的数量。对于每个测试用例:

第一行包含两个整数 mxm_xmym_y (109mx,my109-10^9 \le m_x, m_y \le 10^9),表示地雷的坐标。

第二行包含一个字符串 s1s2sns_1s_2\cdots s_n,长度为 nn (1n1051 \le n \le 10^5, $s_i \in \{\text{`U'}, \text{`D'}, \text{`L'}, \text{`R'}\}$),表示编程到机器人中的字符串。

保证所有测试用例的 nn 的总和不超过 10610^6

Output Format

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

5
1 1
RURULLD
0 5
UUU
0 3
UUU
0 2
UUU
0 0
UUU

LDLRUUR
UUU
Impossible
Impossible
Impossible

Hint

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