Optimization of Combinatorial Circuits

Time Limit : 8 sec, Memory Limit : 131072 KB

Problem A: Optimization of Combinatorial Circuits

Nathan O. Davis is a student at the department of integrated systems. Today, he is attending his digital circuit class. The topic of the lecture is optimization of combinatorial circuits. Combinatorial circuits are digital circuits that implement boolean logics with AND-gates and OR-gates. They usually have multiple inputs and a single output.

At the end of the lecture, hefs got a homework as usual. The task is to write a program that optimizes combina- torial circuits.

The specification of the original (unoptimized) circuit is given in the form of truth-table, for example, as follows:

This table represents a four-input circuit. The first row denotes that when the input b is e0f and the input d is e1f, the output must be e1f. The output exf indicates gdonft careh, that is, it doesnft matter whether the output for the corresponding pattern is e0f or e1f. As a whole, this table represents a circuit that outputs e1f for the inputs that satisfy (¬bd) ∨ (ac ∧ ¬d), either e0f or e1f for the inputs that satisfy (¬bc) ∨ (¬ab) ∨ (ad), and e0f for any other input patterns. How do optimized versions of this circuit look? Here is an example:

The circuit implied by this truth table outputs e1f for the inputs satisfying (cd), and e0f for all the other patterns. You should note that this circuit is consistent with the specification of the original circuit.

You can see the size of the circuit is reduced from the original one. In fact, the circuit above is the most optimized among all the circuits meeting the original specification. Here, we say a circuit is more optimized than another when it has a fewer number of rows in the table. When two circuits have the same number of rows, the one with the fewer number of 0/1s in the table is said to be more optimized.

Now, please write a program doing this optimization to help Nathan!


The input consists of multiple test cases.

The first line of each test case consists of two integers N and M. The integer N (1 ≤ N ≤ 6) is the number of input signals, and M (1 ≤ M ≤ 2N ) is the number of rows of the table.

Then M lines describing the input circuit follow. Each line consists of a string S of the length N and a character C. The string S represents the input pattern. Each character of S is either e0f, e1f, or e-f. The character C is either e1f or exf, meaning that the desired output for the input pattern S is e1f or edonft caref respectively. You may assume that the input contains at least one line with C being e1f

The end of the input is indicated by a line g0 0h.


Output the table denoting the most optimized circuit for each test case. For each row of the table representing the output circuit, you should output a string corresponding to the input pattern in a line. You do not have to write the output specification e1f or exf, since the most optimized circuit has no patterns whose output are ambiguous.

When there are multiple possible solutions, print any one of them. Also, you may print the rows in the table in an arbitrary order.

Each output should be preceded by a line denoting the test case number. Outputs from distinct test cases must be separated by one blank line.

Sample Input

4 5
-0-1 1
1-10 1
-01- x
01-- x
1--1 x
4 11
0000 1
0001 1
0011 1
0100 1
1000 1
1010 1
1011 1
1100 1
1101 1
1110 1
1111 1
0 0

Output for the Sample Input

Case 1:

Case 2:

Source: ACM-ICPC Japan Alumni Group Practice Contest , for World Finals, Tokyo, Japan, 2008-02-24