/*  ExactCover - solving exact cover problems

    On the stdin it expects the representation of the exact cover, where
    each line on the input represents one vector. All vectors should be
    of the same length. The maximum length is NR_POSITIONS. A vector is
    represented by a sequence of 0 and 1. The remainder of the line (after
    skipping spaces) is used as the name for the vector.
    On the stdout it generates the solutions by listing the names of
    the selected vectors on a line per solution found.
    
    This program is refered to at http://www.iwriteiam.nl/D0504.html#25
    
    The implementation makes use of dancing links, a technique suggested
    by D.E. Knuth. See: http://en.wikipedia.org/wiki/Dancing_Links
    
    Copyright (C) 2009 Frans Faase

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.
    
    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.
    
    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

GNU General Public License:
    http://www.iwriteiam.nl/GNU.txt
*/

#include <stdio.h>
#include <string.h>
#include <malloc.h>

struct Vector;
struct Position;

struct Node
{
    Node() : l(this), r(this), d(this), u(this), vector(0), position(0) {}
	void push_back(Node* n)   { n->r = this, n->l = l; l->r = n; l = n; }
	void push_bottom(Node* n) { n->d = this, n->u = u; u->d = n; u = n; }
	void swapout_horz() { l->r = r; r->l = l; }
	void swapin_horz() { l->r = this; r->l = this; }
	void swapout_vert() { u->d = d; d->u = u; }
	void swapin_vert() { u->d = this; d->u = this; }
	Node *l;
	Node *r;
	Node *d;
	Node *u;
    Vector *vector;
    Position *position;
};

struct Vector : public Node
{
    char *name;
};

struct Position : public Node
{
    int nr;
    int nr_vec_left;
};

Node root;
int nr_pos = 0;
int nr_vec = 0;

void read(FILE *f)
{
	char buf[1000];
	
	while (fgets(buf, 1000, f))
	{
		if (nr_pos == 0)
		{
			for (int i = 0; i < 1000 && (buf[i] == '0' || buf[i] == '1'); i++)
				nr_pos++;
			
			for (int i = 0; i < nr_pos; i++)
			{
                Position *position = new Position();
                root.push_back(position);
                position->nr = i;
                position->nr_vec_left = 0;
			}
		}
		
		
		nr_vec++;
        Vector *vector = new Vector;
        root.push_bottom(vector);
		
        char *s = buf;

        Position *position = (Position*)root.r;
		for (int i = 0; i < 1000 && (*s == '0' || *s == '1'); i++, s++)
		{
			if (*s == '1')
			{
				Node *node = new Node();
                position->push_bottom(node);
                vector->push_back(node);
                node->vector = vector;
                node->position = position;
                position->nr_vec_left++;
			}
            position = (Position*)position->r;
		}
		while (*s == ' ')
			s++;
		int l = strlen(s);
		if (s[l-1] == '\n')
			s[--l] = 0;
		vector->name = (char*)malloc(sizeof(char)*(l+1));
		strcpy(vector->name, s);
	}
}

void ignoreVector(Vector* vector, Position* exclude)
{
	vector->swapout_vert();
	
	for (Node* node = vector->r; node != vector; node = node->r)
	{
		if (node->position != exclude)
		{
			node->swapout_vert();
			node->position->nr_vec_left--;
		}
	}
}

void unignoreVector(Vector* vector, Position* exclude)
{
	for (Node* node = vector->l; node != vector; node = node->l)
	{
		if (node->position != exclude)
		{
			node->swapin_vert();
			node->position->nr_vec_left++;
		}
	}

	vector->swapin_vert();
}

void selectPosition(Position* position, Vector* exclude)
{
	position->swapout_horz();
	
	for (Node* node = position->d; node != position; node = node->d)
	{
		if (node->vector != exclude)
			ignoreVector(node->vector, position);
	}
}

void unselectPosition(Position* position, Vector* exclude)
{
	for (Node* node = position->u; node != position; node = node->u)
	{
		if (node->vector != exclude)
			unignoreVector(node->vector, position);
	}

	position->swapin_horz();
}

void selectVector(Vector* vector)
{
	vector->swapout_vert();
	
	for (Node* node = vector->r; node != vector; node = node->r)
		selectPosition(node->position, vector);
}

void unselectVector(Vector* vector)
{
	for (Node* node = vector->l; node != vector; node = node->l)
		unselectPosition(node->position, vector);

	vector->swapin_vert();
}

int nr_solutions = 0;
#define NR_SOLUTIONS_TO_FIND 1

Vector* sol_vectors[1000];
int nr_sol_vectors = 0;

bool solve()
{
	// Found solution if there are no positions left
	if (root.r == &root)
	{
		nr_solutions++;
		
		for (int i = 0; i < nr_sol_vectors; i++)
			printf("%s\n", sol_vectors[i]->name);
		
		return nr_solutions >= NR_SOLUTIONS_TO_FIND;
	}

	// If there is a position that cannot be filled, then stop
	for (Position *position = (Position*)root.r; position != &root; position = (Position*)position->r)
	{
		if (position->nr_vec_left == 0)
			return false;
	}

	// If there is a position with only one possible vector, select this vector	
	for (Position *position = (Position*)root.r; position != &root; position = (Position*)position->r)
	{
		if (position->nr_vec_left == 1)
		{
			Vector *vector = position->d->vector;
			
			sol_vectors[nr_sol_vectors++] = vector;
			selectVector(vector);

			bool result = solve();

			unselectVector(vector);
			nr_sol_vectors--;

			return result;
		}
	}
	
	// No see which vector when selected leaves the largest number of vectors open
	Vector* best_vec = 0;
	int best_nr = 0;
	for (Vector *vector = (Vector*)root.d; vector != &root; vector = (Vector*)vector->d)
	{
		selectVector(vector);
		
		// Evaluate solution
		bool possible = true;
		for (Position *position = (Position*)root.r; position != &root; position = (Position*)position->r)
			if (position->nr_vec_left == 0)
			{
				possible = false;
				break;
			}
		
		if (possible)
		{
			int nr = 0;
			for (Vector *vec = (Vector*)root.d; vec != &root; vec = (Vector*)vec->d)
				nr++;
				
			if (best_vec == 0 || nr > best_nr)
			{
				best_vec = vector;
				best_nr = nr;
			}
		}
		
		unselectVector(vector);
	}
	
	if (best_vec == 0)
		return false;
		
	sol_vectors[nr_sol_vectors++] = best_vec;
	selectVector(best_vec);

	bool result = solve();

	unselectVector(best_vec);
	nr_sol_vectors--;
	
	if (result)
		return true;
		
	ignoreVector(best_vec, 0);
	
	result = solve();
	
	unignoreVector(best_vec, 0);
	
	return result;
}

void print(FILE *f)
{
	for (Vector *vector = (Vector*)root.d; vector != &root; vector = (Vector*)vector->d)
	{
		Node *node = vector->r;
		
		for (Position *position = (Position*)root.r; position != &root; position = (Position*)position->r)
		{
			if (node != vector && node->position == position)
			{
				fprintf(f, "1");
				node = node->r;
			}
			else
				fprintf(f, "0");
		}
		fprintf(f, " %s\n", vector->name);
	}
}

int main(int argc, char* argv[])
{
	read(stdin);
	solve();
}