[ICPC 2020 Nanjing R] Evil Coordinate

Luogu
IDLGP9626
Time1000ms
Memory256MB
DifficultyP3
2020Special JudgeO2优化ICPC南京
A robot is standing on an infinite 2-dimensional plane. Programmed with a string $s_1s_2\cdots s_n$ of length $n$, where $s_i \in \{\text{`U'}, \text{`D'}, \text{`L'}, \text{`R'}\}$, the robot will start moving from $(0, 0)$ and will follow the instructions represented by the characters in the string. More formally, let $(x, y)$ be the current coordinate of the robot. Starting from $(0, 0)$, the robot repeats the following procedure $n$ times. During the $i$-th time: - If $s_i = \text{`U'}$ the robot moves from $(x, y)$ to $(x, y+1)$; - If $s_i = \text{`D'}$ the robot moves from $(x, y)$ to $(x, y-1)$; - If $s_i = \text{`L'}$ the robot moves from $(x, y)$ to $(x-1, y)$; - If $s_i = \text{`R'}$ the robot moves from $(x, y)$ to $(x+1, y)$.- However, there is a mine buried under the coordinate $(m_x, m_y)$. If the robot steps onto $(m_x, m_y)$ during its movement, it will be blown up into pieces. Poor robot! Your task is to rearrange the characters in the string in any order, so that the robot will not step onto $(m_x, m_y)$. ## Input There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case: The first line contains two integers $m_x$ and $m_y$ ($-10^9 \le m_x, m_y \le 10^9$) indicating the coordinate of the mine. The second line contains a string $s_1s_2\cdots s_n$ of length $n$ ($1 \le n \le 10^5$, $s_i \in \{\text{`U'}, \text{`D'}, \text{`L'}, \text{`R'}\}$) indicating the string programmed into the robot. It's guaranteed that the sum of $n$ of all test cases will not exceed $10^6$. ## Output For each test case output one line. If a valid answer exists print the rearranged string, otherwise print ``Impossible`` instead. If there are multiple valid answers you can print any of them. [samples]
Samples
Input #1
5
1 1
RURULLD
0 5
UUU
0 3
UUU
0 2
UUU
0 0
UUU
Output #1
LDLRUUR
UUU
Impossible
Impossible
Impossible
API Response (JSON)
{
  "problem": {
    "name": "[ICPC 2020 Nanjing R] Evil Coordinate",
    "description": {
      "content": "A robot is standing on an infinite 2-dimensional plane. Programmed with a string $s_1s_2\\cdots s_n$ of length $n$, where $s_i \\in \\{\\text{`U'}, \\text{`D'}, \\text{`L'}, \\text{`R'}\\}$, the robot will st",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9626"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A robot is standing on an infinite 2-dimensional plane. Programmed with a string $s_1s_2\\cdots s_n$ of length $n$, where $s_i \\in \\{\\text{`U'}, \\text{`D'}, \\text{`L'}, \\text{`R'}\\}$, the robot will st...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments