/*  ExactCoverTrivial - solving exact cover problems with a "trivial" heuristic.

    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 put is generates the solutions by listing the names 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
    
    The algorithm makes use of the "trivial" heuristic which selects a
    random vector (the first) from the first position with the lowest
    number of vectors left.
    
    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>
#include <time.h>


#define NR_POSITIONS 1000

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
{
    Vector(long n) : nr(n), next_ignored(0) {}
    char *name;
    long nr;
    Vector* next_ignored;
};

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

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

void read(FILE *f)
{
    char buf[2*NR_POSITIONS];
    
    while (fgets(buf, 2*NR_POSITIONS, f))
    {
        if (nr_pos == 0)
        {
            for (int i = 0; i < NR_POSITIONS && (buf[i] == '0' || buf[i] == '1'); i++)
                nr_pos++;
            
            nr_pos_with_zero_vec = 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(nr_vec);
        root.push_bottom(vector);
        
        char *s = buf;

        Position *position = (Position*)root.r;
        for (int i = 0; i < NR_POSITIONS && (*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;
                if (position->nr_vec_left++ == 0)
                    nr_pos_with_zero_vec--;
            }
            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();
            if (--node->position->nr_vec_left == 0)
                nr_pos_with_zero_vec++;
        }
    }
}

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

    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();
    //vector->hot = false;
}

class IgnoredVectors
{
public:
    IgnoredVectors() : _ignored(0) {}
    
    void add(Vector* vector)
    {
        vector->next_ignored = _ignored;
        _ignored = vector;
        
        ignoreVector(vector, 0);
    }
    
    ~IgnoredVectors()
    {
        while (_ignored != 0)
        {
            Vector* next_ignored = _ignored->next_ignored;
            _ignored->next_ignored = 0;
            unignoreVector(_ignored, 0);
            _ignored = next_ignored;
        }
    }

private:
    Vector* _ignored;
};


void reduce(IgnoredVectors &ignoredVectors)
{
    for (bool progress = true; progress;)
    {
        progress = false;
        
        for (Position *position1 = (Position*)root.r; position1 != &root; position1 = (Position*)position1->r)
            for (Position *position2 = (Position*)root.r; position2 != &root; position2 = (Position*)position2->r)
                if (position1->nr_vec_left < position2->nr_vec_left)
                {
                    if (position1->nr_vec_left == 0)
                    {
                        return; // -- no solution possible
                    }
                
                    bool implied = true;

                    Node* node2 = position2->d;
                    for (Node* node1 = position1->d; node1 != position1; node1 = node1->d)
                    {
                        int vec_nr = node1->vector->nr;
                        
                        while (node2 != position2 && node2->vector->nr < vec_nr)
                            node2 = node2->d;
                            
                        if (node1->vector != node2->vector)
                        {
                            implied = false;
                            break;
                        }
                    }

                    if (implied)
                    {
                        Vector *next_vector = 0;
                        for (Vector *vector = (Vector*)root.d; vector != &root; vector = next_vector)
                        {
                            next_vector = (Vector*)vector->d;
                            
                            bool has_position1 = false;
                            bool has_position2 = false;
                            
                            for (Node* node = vector->r; node != vector; node = node->r)
                            {
                                if (node->position == position1)
                                    has_position1 = true;
                                if (node->position == position2)
                                    has_position2 = true;
                            }
                            
                            if (!has_position1 && has_position2)
                            {
                                ignoredVectors.add(vector);
                            }                                    
                        }
                        
                        progress = true;
                    }
                }
    }    
}

bool possible()
{
    if (nr_pos_with_zero_vec > 0)
        return false;
        
    for (Position *position = (Position*)root.r; position != &root; position = (Position*)position->r)
        if (position->nr_vec_left == 1)
        {
            Vector *vector_with_one = position->d->vector;
            
            selectVector(vector_with_one);
            
            bool pos = possible();
            
            unselectVector(vector_with_one);
            
            return pos;
        }
    return true;
}

int nr_solutions = 0;

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

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

    IgnoredVectors ignoredVectors;
    for(;;)
    {
        // If there is a position that cannot be filled, then stop
        if (nr_pos_with_zero_vec > 0)
            return;
        
        Position* best_pos = 0;
        int best_nr = 0;
        for (Position *position = (Position*)root.r; position != &root; position = (Position*)position->r)
        {
            if (best_pos == 0 || position->nr_vec_left < best_nr)
            {
                best_pos = position;
                best_nr = position->nr_vec_left;
                if (best_nr == 1)
                    break;
            }
        }

        if (best_nr == 0)
        {
            fprintf(stderr, "ERROR\n");
            return;
        }
        
        Vector* sel_vector = best_pos->d->vector;
        sol_vectors[nr_sol_vectors++] = sel_vector;
        selectVector(sel_vector);
    
        solve();
    
        unselectVector(sel_vector);
        nr_sol_vectors--;
        
        if (best_nr == 1)
            return;
            
        ignoredVectors.add(sel_vector);

    }        
}

int main(int argc, char* argv[])
{
    read(stdin);
    
    IgnoredVectors ignoredVectors;
    reduce(ignoredVectors);

    for (bool progress = true; progress; )
    {
        progress = false;
        
        for (Vector *vector = (Vector*)root.d; vector != &root; vector = (Vector*)vector->d)
        {
            selectVector(vector);
            
            // Evaluate solution
            bool pos = possible();

            unselectVector(vector);
            
            if (!pos)
            {
                ignoredVectors.add(vector);
                progress = true;
            }
        }
    }

    solve();
}