상당히 난해한 대결

당신은 가위바위보 대회를 조직해 달라는 요청을 받았다. 대회는 단판 승자 진출 방식으로 N라운드 동안 진행되며, $2^{N}$명의 선수가 참가한다.

처음에 선수들은 당신이 지정한 순서대로 왼쪽에서 오른쪽으로 줄을 선다. 각 라운드에서는 줄의 왼쪽부터 첫 번째 선수와 두 번째 선수가 서로 경기를 하고, 세 번째 선수와 네 번째 선수(존재한다면)가 서로 경기를 하는 식으로 계속되며, 이 모든 경기는 동시에 진행된다. 이 경기들의 승자는 같은 상대적 순서를 유지한 채 줄에 남고, 패자는 줄을 떠나 집으로 돌아간다. 그런 다음 새로운 라운드가 시작된다. 줄에 선수가 하나만 남을 때까지 이 과정이 계속되며, 그 선수가 우승자로 선언된다.

각 가위바위보 경기에서 두 선수는 각각 바위, 보, 가위 중 하나를 몰래 선택한 다음 서로의 선택을 비교한다. 바위는 가위를 이기고, 가위는 보를 이기며, 보는 바위를 이긴다. 한 선수의 선택이 다른 선수의 선택을 이기면 그 선수가 승리하고 경기가 끝난다. 그러나 선수들이 같은 것을 선택하면 무승부가 되며, 승자가 나올 때까지 다시 선택하며 경기를 계속해야 한다.

당신은 올해의 선수들이 고집이 세고 전략적이지 않다는 것을 알고 있다. 각 선수에게는 선호하는 동작이 하나 있으며, 상대가 무엇을 하든 모든 경기에서 그 동작만 낸다. 이 때문에 같은 동작을 내는 두 선수가 맞붙으면 계속 무승부가 나서 경기가 영원히 이어진다! 이런 일이 발생하면 대회는 절대 끝나지 않고 당신은 웃음거리가 될 것이다.

올해는 바위를 선호하는 선수가 R명, 보를 선호하는 선수가 P명, 가위를 선호하는 선수가 S명 있다. 이를 알고 있는 당신은 대회가 끝까지 진행되어 단 한 명의 우승자를 내도록 보장하는, 즉 어떤 경기에서도 무승부가 발생하지 않는 줄 순서를 만들고자 한다. 상사는 그러한 모든 줄 순서를 왼쪽에서 오른쪽 순서로 적은 목록을 만들고(바위, 보, 가위를 선호하는 선수는 각각 R, P, S로 나타낸다), 그 목록을 알파벳순으로 정렬하라고 했다.

상사는 귀찮아하며 목록의 첫 번째 줄 순서를 고를 것이다. 그것은 무엇인가? 아니면 무승부를 피하는 것이 IMPOSSIBLE하다고 상사에게 말해야 하는가?

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1 GB. R + P + S = $2^{N}$. 0 ≤ R ≤ $2^{N}$. 0 ≤ P ≤ $2^{N}$. 0 ≤ S ≤ $2^{N}$.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ T ≤ 25. 1 ≤ N ≤ 3.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ T ≤ 75. 1 ≤ N ≤ 12.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어지며, 각 줄은 하나의 테스트 케이스를 나타낸다. 각 테스트 케이스는 위의 문제 설명에 기술된 네 정수 N, R, P, S로 이루어진다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y은 IMPOSSIBLE이거나 문제를 해결하는 줄의 초기 순서 중 알파벳순으로 가장 앞선 것을 나타내는 길이 $2^{N}$의 문자열이다. 줄 순서의 모든 문자는 R, P, S 중 하나여야 하며, R가 R개, P가 P개, S가 S개 있어야 한다.

예제 케이스 #1에는 선수가 둘뿐이며 대회는 한 라운드로 이루어진다. 두 선수가 어떤 순서로 줄을 서는지는 중요하지 않으며, 보를 내는 선수가 바위를 내는 선수를 이긴다. 당신은 상사에게 알파벳순으로 정렬된 목록 PR, RP를 주며, 첫 번째 원소는 PR이다.

예제 케이스 #2에서는 단 두 선수 모두 바위를 내므로 무승부를 피할 수 없다.

예제 케이스 #3에는 선수가 넷 있으며 대회는 두 라운드 동안 진행된다. 첫 라운드에서 첫 번째 선수(보)는 두 번째 선수(가위)에게 지고, 세 번째 선수(바위)는 네 번째 선수(가위)를 이긴다. 두 번째 라운드의 줄 순서는 PR가 되며, 남은 첫 번째 선수(보)가 남은 다른 선수(바위)를 이기므로 대회는 무승부 없이 우승자를 내고 끝난다.

다음은 예제 케이스 #3의 대회를 나타낸 그림이다.

PSSR와 같은 다른 줄 순서도 상사에게 주는 목록에 나타나지만, PSRS가 알파벳순으로 가장 앞선다.

예제 케이스 #4에서 첫 라운드에 무승부가 없도록 구성하는 유일한 방법은 바위를 내는 선수 한 명과 가위를 내는 선수 한 명으로 이루어진 경기를 두 개 만드는 것이다. 그러나 두 경기 모두 바위를 내는 선수가 승리하며, 이 두 승자가 서로 맞붙으면 무승부가 된다.