Go++ (Large)

The Go language was designed to have a simple API and to support multi-threading. The Code Jam team wants to push these goals to the limit, so we are proposing a new language called Go++.

The Go++ language uses one register, which stores one boolean value (0 or 1). This register is initialized to 0. The language has three instructions:

• 0, which sets the register to 0.
• 1, which sets the register to 1.
• ?, which prints the current register value.

To support multi-threading, two different Go++ programs may run simultaneously while sharing the one register. Each instruction executes atomically, that is, one instruction must completely finish before the next instruction can start. However, the two programs may be interleaved in any way that preserves the relative order within each program.

For example, here are the only six ways in which the two programs 1? and ?0 could be executed together. The instructions of the second program are wrapped in square brackets to distinguish them from the instructions of the first program.

• [?][0]1?, which prints 01. (Remember that the register is initialized to 0.)
• [?]1[0]?, which prints 00.
• [?]1?[0], which prints 01.
• 1[?][0]?, which prints 10.
• 1[?]?[0], which prints 11.
• 1?[?][0], which prints 11.

The printed string always consists of 0s and 1s, since the register can only hold 0 or 1.

Usually, programmers write programs to produce a desired output, but your task is to write two programs that won't produce an undesired output. You are given a "bad" string B of length L and a set G of N "good" strings, all of length L. You must produce two Go++ programs (not necessarily of the same length) which, when run in the way described here, could produce every string in G but could not produce the string B, no matter how they are interleaved. It is fine if the programs could also produce other strings that are not B and not in G. There must be a combined total of exactly L ? instructions in the two programs, and the combined number of instructions in the two programs must not exceed 200.

For example, for B = 11 and G = { 10, 00 }, the programs ? and 10?1 would be one valid answer. They can produce every string in G, but they cannot produce B, no matter how they are interleaved. (They can also produce the string 01, which is not B and is not in G, but that is fine.) However, the programs 1? and ?0 would not be a valid answer, since (as shown above) they can produce B. The programs 00 and ?? would not be a valid answer either, since they cannot produce every string in G.

Produce two programs that satisfy the conditions, or determine that the task is IMPOSSIBLE.

The first line of the input gives the number of test cases, T. T test cases follow; each consists of three lines. The first line of each test case has two integers N and L: the number of strings in G, and the length of B and of the strings in G. The second line has N different strings of length L separated by spaces: the strings in G. The third line has one string of length L: the bad string B. B and all of the strings in G consist only of 0s and 1s.

Limits

• $1 \le T \le 100$
• $1 \le N \le 100$
• $1 \le L \le 50$
• All strings in G are different.
• B may be any string consisting of 0s and 1s.

For each test case, output one line. If no pair of programs satisfies the conditions, output Case #x: IMPOSSIBLE. Otherwise, output Case #x: y z, where x is the test case number (starting from 1) and y and z are the two programs built by the rule below.

Let $b_i$ be the $i$-th character of B, and let $\bar{b}_i$ be the flipped character (1 if $b_i$ is 0, and 0 if $b_i$ is 1).

• y is the program of length $2L$ formed by concatenating $\bar{b}_i$ followed by ? for $i = 1, 2, \ldots, L$ in order.
• If $L \ge 2$, z is the program of length $2L-2$ formed by concatenating $\bar{b}_i$ followed by $b_i$ for $i = 1, 2, \ldots, L-1$ in order. If $L = 1$, z is the single instruction $\bar{b}_1$.

Whenever some pair of programs satisfies the conditions, the pair built by this rule also satisfies them. For example, for B = 11, y is 0?0? and z is 01.

Sample case #1 is the one described in the problem statement. The programs ? and 10?1 from the statement also satisfy the conditions, but the required output follows the rule above and is 0?0? 01.

Sample case #3 is obviously IMPOSSIBLE because B is in G.