#include <iostream>
#include <cassert>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <bitset>
using namespace std;

void add_to( set<string>& v, string& s, int i=0 )
{
	for(; i!=s.size(); ++i)
		if( s[i] == '-' )
		{
			s[i] = '0'; add_to(v, s, i+1);
			s[i] = '1'; add_to(v, s, i+1);
			s[i] = '-'; return;
		}
	v.insert(s);
}

bool merge( const string& a, const string& b, string& result )
{
	int dc = 0;
	for(int i=0; i!=a.size(); ++i)
		if( a[i] != b[i] )
		{
			if( ++dc > 1 || a[i]=='-' || b[i]=='-' )
				return false;
			result    = a;
			result[i] = '-';
		}
	return dc==1;
}

// ---------------------------------------------------------------------------

bool cover( const string& pat, const string& term )
{
	for(int i=0; i!=pat.size(); ++i)
		if( pat[i]!='-' && pat[i]!=term[i] )
			return false;
	return true;
}

struct MinCover
{
// in/out
	typedef bitset<128> bits;
	struct Pattern { string s; bits b; int n01; };
	vector<Pattern> prin;
	bits allmask;
	int TS;

	MinCover( const vector<string>& p, const set<string>& t ) : TS(t.size())
	{
		for(int i=0; i!=p.size(); ++i)
		{
			bits bs;
			for(set<string>::const_iterator it=t.begin(); it!=t.end(); ++it)
				bs<<=1, bs[0]=cover(p[i], *it);
			Pattern pat = {p[i], bs, p[i].size()-count(p[i].begin(),p[i].end(),'-')};
			prin.push_back( pat );
		}
		for(int t=0; t!=TS; ++t)
			allmask[t] = 1;
	}

// optimization
	bool opt_1() // Choose neccesary principal terms
	{
		for(int p=0; p!=prin.size(); ++p)
		{
			bits reason_de_etre = prin[p].b & allmask;
			for(int q=0; q!=prin.size(); ++q) if(q!=p)
				reason_de_etre &= ~prin[q].b;

			if( reason_de_etre.any() )
			{
				cout << prin[p].s << endl;

				allmask &= ~prin[p].b;
				prin.erase( prin.begin()+p );
				return true;
			}
		}
		return false;
	}

	bool opt_2() // remove redundant principal terms
	{
		for(int p=0; p!=prin.size(); ++p)
			if( (prin[p].b&allmask).none() )
				{prin.erase( prin.begin()+p ); return true;}

		for(int p=0; p!=prin.size(); ++p)
		for(int q=0; q!=prin.size(); ++q) if(p!=q && prin[p].n01 >= prin[q].n01)
			if( ((prin[p].b & prin[q].b)&allmask) == (prin[p].b&allmask) )
				{prin.erase( prin.begin()+p ); return true;}
		return false;
	}

	bool opt_3() // remove redundant terms
	{
		for(int t=0; t!=TS; ++t) if( allmask[t] )
		for(int s=0; s!=TS; ++s) if( allmask[s] && t!=s )
		{
			for(int p=0; p!=prin.size(); ++p)
				if( prin[p].b[t] < prin[p].b[s] )
					goto nextS;
			allmask.reset(t);
			return true;
		nextS:;
		}
		return false;
	}

// main routine: iterative deepening
	void print_best()
	{
		cur_best_num01 = 99999;
		for(int n=0; n<=prin.size() && cur_best_num01==99999; ++n)
			dfs( n, 0, allmask );
		for(int i=0; i!=cur_best.size(); ++i)
			cout << cur_best[i] << endl;
	}

	vector<string> stk,  cur_best;
	int            cur_best_num01;

	void dfs( int n, int num01, bits mask, int i=0 )
	{
		if( n == 0 ) {
			if( mask.none() && num01 < cur_best_num01 )
				{cur_best_num01 = num01; cur_best = stk;}
			return;
		}

		stk.push_back( prin[i].s );
		dfs(n-1, num01+prin[i].n01, mask&~prin[i].b, i+1);
		stk.pop_back();
		if( i+n < prin.size() )
			dfs(n, num01, mask, i+1);
	}
};

int main()
{
	for(int NV,NR,nCase=1; cin>>NV>>NR, NV|NR; ++nCase)
	{
		assert( 1<=NV && NV<=6 );
		assert( 0<=NR && NR<=(1<<NV) );

		// read the input --------------------------------------------------

		set<string> must, may;
		while(NR--)
		{
			string pat,v; cin>>pat>>v;

			if( v == "1" )
				add_to(must, pat);
			add_to(may, pat);
		}

		// calc principal terms --------------------------------------------

		vector<string> prin;

		while( !may.empty() )
		{
			set<string> may2;

			string c;
			set<string> used;
			for(set<string>::iterator a=may.begin(); a!=may.end(); ++a)
			for(set<string>::iterator b=a;           b!=may.end(); ++b)
				if( merge(*a, *b, c) )
				{
					used.insert(*a);
					used.insert(*b);
					may2.insert(c);
				}

			for(set<string>::iterator i=may.begin(); i!=may.end(); ++i)
				if( !used.count(*i) )
					prin.push_back(*i);
			may.swap(may2);
		}

		// calc minimum cover ----------------------------------------------

		if(nCase>1) cout << endl;
		cout << "Case " << nCase << ":" << endl;

		MinCover mc( prin, must );
		while( mc.opt_1() || mc.opt_2() || mc.opt_3() ) {}
		mc.print_best();
	}
}