Go++ (Large)

Go 언어는 API가 단순하고 멀티스레딩을 지원하도록 설계되었다. 코드 잼 팀은 이 목표를 극한까지 밀어붙이려고 Go++라는 새 언어를 제안한다.

Go++에는 불리언 값(0 또는 1) 하나를 저장하는 레지스터가 하나 있고, 이 레지스터의 초깃값은 0이다. 명령은 세 가지다.

• 0: 레지스터를 0으로 설정한다.
• 1: 레지스터를 1로 설정한다.
• ?: 레지스터의 현재 값을 출력한다.

멀티스레딩을 지원하기 위해 서로 다른 Go++ 프로그램 두 개가 레지스터 하나를 공유하며 동시에 실행된다. 각 명령은 원자적으로 실행된다. 즉 한 명령이 완전히 끝나야 다음 명령이 시작된다. 두 프로그램의 명령은 각 프로그램 안의 순서만 지킨다면 어떤 식으로든 섞여서 실행될 수 있다.

예를 들어 두 프로그램 1?과 ?0을 함께 실행하는 방법은 아래 여섯 가지뿐이다. 두 번째 프로그램의 명령은 대괄호로 감싸 첫 번째 프로그램의 명령과 구분했다.

• [?][0]1?: 01을 출력한다. (레지스터의 초깃값은 0이다.)
• [?]1[0]?: 00을 출력한다.
• [?]1?[0]: 01을 출력한다.
• 1[?][0]?: 10을 출력한다.
• 1[?]?[0]: 11을 출력한다.
• 1?[?][0]: 11을 출력한다.

레지스터가 가질 수 있는 값은 0과 1뿐이므로 출력되는 문자열은 항상 0과 1로만 이루어진다.

보통 프로그래머는 원하는 출력을 내는 프로그램을 작성하지만, 이 문제에서는 원하지 않는 출력을 내지 않는 프로그램 두 개를 작성해야 한다. 길이가 L인 "나쁜" 문자열 B 하나와, 길이가 모두 L인 "좋은" 문자열 N개로 이루어진 집합 G가 주어진다. 두 프로그램을 위에서 설명한 방식으로 실행했을 때 G의 모든 문자열을 출력할 수 있어야 하고, B는 어떤 순서로 섞어 실행해도 출력할 수 없어야 한다. 두 프로그램의 길이는 같지 않아도 된다. B도 아니고 G에도 없는 문자열을 출력할 수 있는 것은 상관없다. 두 프로그램에 들어 있는 ? 명령은 합쳐서 정확히 L개여야 하고, 두 프로그램의 명령 수를 합하면 200을 넘으면 안 된다.

예를 들어 B = 11, G = { 10, 00 }이면 두 프로그램 ?과 10?1은 올바른 답 중 하나다. 이 두 프로그램은 G의 모든 문자열을 출력할 수 있고, 어떻게 섞어 실행해도 B는 출력할 수 없다. (B도 아니고 G에도 없는 01도 출력할 수 있지만 문제없다.) 반면 두 프로그램 1?과 ?0은 위에서 본 것처럼 B를 출력할 수 있으므로 올바른 답이 아니다. 두 프로그램 00과 ??는 G의 모든 문자열을 출력할 수는 없으므로 역시 올바른 답이 아니다.

조건을 만족하는 두 프로그램을 만들거나, 그런 프로그램이 없으면(IMPOSSIBLE) 이를 판정하라.

첫째 줄에 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 세 줄로 이루어진다. 첫째 줄에는 G에 속한 문자열의 수 N과 문자열의 길이 L이 주어진다. 둘째 줄에는 G에 속한 길이 L의 서로 다른 문자열 N개가 공백으로 구분되어 주어진다. 셋째 줄에는 길이 L의 나쁜 문자열 B가 주어진다. B와 G의 모든 문자열은 0과 1로만 이루어져 있다.

제한

• $1 \le T \le 100$
• $1 \le N \le 100$
• $1 \le L \le 50$
• G의 문자열은 모두 서로 다르다.
• B는 0과 1로 이루어진 어떤 문자열이든 될 수 있다.

각 테스트 케이스마다 한 줄을 출력한다. 조건을 만족하는 두 프로그램이 없으면 Case #x: IMPOSSIBLE을 출력한다. 그렇지 않으면 Case #x: y z를 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y와 z는 아래 규칙으로 만든 두 프로그램이다.

B의 $i$번째 문자를 $b_i$라 하고, $b_i$를 뒤집은 문자(0이면 1, 1이면 0)를 $\bar{b}_i$라 하자.

• y는 $i = 1, 2, \ldots, L$ 순서로 $\bar{b}_i$와 ?를 이어 붙인 길이 $2L$의 프로그램이다.
• $L \ge 2$이면 z는 $i = 1, 2, \ldots, L-1$ 순서로 $\bar{b}_i$와 $b_i$를 이어 붙인 길이 $2L-2$의 프로그램이다. $L = 1$이면 z는 명령 하나 $\bar{b}_1$로 이루어진 프로그램이다.

조건을 만족하는 두 프로그램이 존재하면, 이 규칙으로 만든 두 프로그램도 항상 조건을 만족한다. 예를 들어 B = 11이면 y는 0?0?, z는 01이다.

예제의 첫 번째 테스트 케이스는 본문에서 설명한 경우와 같다. 본문의 두 프로그램 ?과 10?1도 조건을 만족하지만, 출력은 위 규칙에 따라 0?0? 01이어야 한다.

세 번째 테스트 케이스는 B가 G에 들어 있으므로 당연히 IMPOSSIBLE이다.