Evil Coordinate
면접 대비시간 제한1초메모리 제한512 MB
주어진 지뢰 칸을 로봇이 지나가지 않도록 이동 문자열의 순서를 바꾸고, 불가능하면 Impossible을 출력한다.
문제
A robot is standing on an infinite 2-dimensional plane. Programmed with a string of length , where , the robot will start moving from and will follow the instructions represented by the characters in the string.
More formally, let be the current coordinate of the robot. Starting from , the robot repeats the following procedure times. During the -th time:
- If the robot moves from to ;
- If the robot moves from to ;
- If the robot moves from to ;
- If the robot moves from to .
However, there is a mine buried under the coordinate . If the robot steps onto 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 .
입력
There are multiple test cases. The first line of the input contains an integer indicating the number of test cases. For each test case:
The first line contains two integers and () indicating the coordinate of the mine.
The second line contains a string of length (, ) indicating the string programmed into the robot.
It's guaranteed that the sum of of all test cases will not exceed .
출력
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.