아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Evil Coordinate

면접 대비

시간 제한1초메모리 제한512 MB

요약
주어진 지뢰 칸을 로봇이 지나가지 않도록 이동 문자열의 순서를 바꾸고, 불가능하면 Impossible을 출력한다.
난이도

보통10점 중 7점

유형
그리디, 구현, 완전 탐색, 시뮬레이션
정답자
아직 제출이 없습니다

문제

A robot is standing on an infinite 2-dimensional plane. Programmed with a string s_1s_2⋯s_ns\_1s\_2\cdots s\_n of length nn, where s_i∈’U’,’D’,’L’,’R’s\_i \in \\{\text{'U'}, \text{'D'}, \text{'L'}, \text{'R'}\\}, the robot will start moving from (0,0)(0, 0) and will follow the instructions represented by the characters in the string.

More formally, let (x,y)(x, y) be the current coordinate of the robot. Starting from (0,0)(0, 0), the robot repeats the following procedure nn times. During the ii-th time:

  • If s_i=’U’s\_i = \text{'U'} the robot moves from (x,y)(x, y) to (x,y+1)(x, y+1);
  • If s_i=’D’s\_i = \text{'D'} the robot moves from (x,y)(x, y) to (x,y−1)(x, y-1);
  • If s_i=’L’s\_i = \text{'L'} the robot moves from (x,y)(x, y) to (x−1,y)(x-1, y);
  • If s_i=’R’s\_i = \text{'R'} the robot moves from (x,y)(x, y) to (x+1,y)(x+1, y).

However, there is a mine buried under the coordinate (m_x,m_y)(m\_x, m\_y). If the robot steps onto (m_x,m_y)(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)(m\_x, m\_y).

입력

There are multiple test cases. The first line of the input contains an integer TT indicating the number of test cases. For each test case:

The first line contains two integers m_xm\_x and m_ym\_y (−109≤m_x,m_y≤109-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⋯s_ns\_1s\_2\cdots s\_n of length nn (1≤n≤1051 \le n \le 10^5, s_i∈’U’,’D’,’L’,’R’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 nn of all test cases will not exceed 10610^6.

출력

For each test case output one line. If a valid answer exists print the rearranged string, otherwise print "Impossible" (without quotes) instead. If there are multiple valid answers you can print any of them.

예제1

  1. 예제 1

    입력
    5
    1 1
    RURULLD
    0 5
    UUU
    0 3
    UUU
    0 2
    UUU
    0 0
    UUU
    
    예상 출력
    LDLRUUR
    UUU
    Impossible
    Impossible
    Impossible