Go++ (Small)

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.

Simple, right? To support multi-threading, we allow two different Go++ programs to run simultaneously while sharing the one register. Each instruction executes atomically: 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. Each instruction of the second program is followed by an apostrophe (') to distinguish it from the instructions of the first program.

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

The output string always consists of 0s and 1s, and never ?s, since ? is not a state the register can be in.

Usually, programmers write programs to produce a desired output, but your task is to write two programs that won't produce an undesired output. Specifically, 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 all of the strings in G, but could not produce the string B. 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. 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 are 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 are not a valid answer, since (as shown above) they can produce B. The programs 00 and ?? are not 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 the string 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 consists entirely of 1s.

For each test case, output one line.

If no pair of programs satisfies the conditions, output Case #x: IMPOSSIBLE, where x is the test case number (starting from 1).

Otherwise, output Case #x: y z, where y and z are two programs that satisfy the conditions. The combined number of instructions in the two programs must not exceed 200, each program must contain at least one instruction, and the two programs must contain a combined total of exactly L ? instructions. Because several answers can be valid, you must output exactly this pair:

• y is 10 repeated $L-1$ times, followed by ?1.
• z is 0 followed by $L-1$ copies of ?.

Whenever any valid answer exists, this pair also satisfies the conditions. For example, for L = 3 the line is Case #x: 1010?1 0??.

Sample case #1 is the one described in the problem statement. Under the output rule, its answer is 10?1 0?.

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