/*	This program solves the exact cover problem.
	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 1000. 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 put is generates the solutions (up to NR_SOLUTIONS_TO_FIND)
	by listing the names (each followed by '|') of the selected vectors on a
	line per solution found.
	
	The implementation makes use of dancing links, a technique suggested by
	D.E. Knuth. See: http://en.wikipedia.org/wiki/Dancing_Links
*/

#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);
		while (s[l-1] < ' ')
			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 10000

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|", sol_vectors[i]->name);
		printf("\n");
		
		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;
		}
	}
	
	Vector* best_vec = 0;
	int best_nr = 0;
	for (Vector *vector = (Vector*)root.d; vector != &root; vector = (Vector*)vector->d)
	{
		int nr = 0;
		for (Node* node = vector->r; node != vector; node = node->r)
			nr += node->position->nr_vec_left;
		
		if (best_vec == 0 || nr < best_nr)
		{
			best_vec = vector;
			best_nr = nr;
		}
	}

	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();
}