/*
From David Applegate, Feb 09 2008

This reads a file of generators specified as a command line argument,
or from stdin if no argument is given.  

To compile:
g++ -o a135463 a135463.cc

Examples of lists of generators:

cat A134948.gen
0 1
1 1
2 2
3 6
4 24
5 120
6 720
7 5040
8 40320
9 362880

cat A134962.gen
1 1
2 4
3 9
4 16
5 25
6 36
7 49
8 64
9 81

cat A135463.gen
1 1 1
2 4 8
3 9 27
4 16 64
5 25 125
6 36 216
7 49 343
8 64 512
9 81 729

cat A135464.gen
1 1
2 11

For example,
   A135463 A134439.gen
generates terms from A134439, and
   A135463 A134439.gen | head -300 | awk '{print NR, $0;}' > b134439.txt
generates a b-file.

I fudged a bit for A134439 and A134692 - the code is designed to just
go for closure, so that, say, since 7 doesn't occur in any square, you
can get a valid entry that omits 7.  For these, I just used a single
generator rule which listed all squares (or cubes).

cat A134439.gen
1 2 3 4 5 6 7 8 9 1 4 9 16 25 36 49 64 81

cat A134692.gen
1 2 3 4 5 6 7 8 9 1 8 27 64 125 216 343 512 729

*/

#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

struct entry {
  struct adjentry {
    string add;
    vector<entry>::iterator to;
    
    adjentry (const string& add_in, vector<entry>::iterator to_in) :
      add (add_in), to (to_in) {}
  };
  
  string val;
  int count;
  size_t lowerbound;
  vector<adjentry> adj;

  entry (const string& val_in) : val (val_in), count (0), lowerbound (0) {}
};

struct entryset {
  size_t tot_lowerbound;
  vector<entry> entries;
};

struct NumberCmp {
  bool operator() (const string& a, const string& b) const {
    if (a.length() != b.length()) return (a.length() < b.length());
    return (a < b);
  }
};

void build_square_cube (set<string>& vals)
{
  for (int d=1; d <= 9; ++d) {
    ostringstream os;
    os << d;
    vals.insert (os.str());
    ostringstream os2;
    os2 << d*d;
    vals.insert (os2.str());
    ostringstream os3;
    os3 << d*d*d;
    vals.insert (os3.str());
  }
}

void prep_entries (const set<string>& vals, vector<entry>& puz, size_t& lb)
{
  puz.clear();
  
  for (set<string>::const_iterator i = vals.begin(); i != vals.end(); ++i) {
    bool is_substr = false;
    for (set<string>::const_iterator j = vals.begin(); j != vals.end(); ++j) {
      if (i == j) continue;
      size_t loc = j->find (*i);
      if (loc != string::npos) {
	is_substr = true;
	break;
      }
    }
    if (is_substr && i->length() != 1) continue;

    puz.push_back (*i);
    if (is_substr) {
      puz.back().count = 1;
    } else {
      puz.back().count = 0;
    }
  }

  for (vector<entry>::iterator i = puz.begin(); i != puz.end(); ++i) {
    if (i->val.length() == 1) {
      continue;
    }
    for (vector<entry>::iterator j = puz.begin(); j != puz.end(); ++j) {
      if (i == j) continue;

      for (size_t n = min(i->val.length(), j->val.length()) - 1; n > 0; --n) {
	if (i->val.substr (i->val.length() - n, n) == j->val.substr(0,n)) {
	  i->adj.push_back (entry::adjentry (j->val.substr(n, j->val.length() - n), j));
	}
      }
    }
  }
  for (vector<entry>::iterator i = puz.begin(); i != puz.end(); ++i) {
    if (i->count == 1) {
      i->lowerbound = 0;
    } else {
      i->lowerbound = i->val.length();
    }
  }

  for (vector<entry>::iterator i = puz.begin(); i != puz.end(); ++i) {
    for (vector<entry::adjentry>::iterator j = i->adj.begin(); j != i->adj.end(); ++j) {
      if (j->add.length() < j->to->lowerbound) j->to->lowerbound = j->add.length();
    }
  }

  lb = 0;
  for (vector<entry>::iterator i = puz.begin(); i != puz.end(); ++i) {
    lb += i->lowerbound;
  }
}

void gen_numbers (size_t len, const string& s, vector<entry>& puz, size_t& lb,
		  entry& n, set<string,NumberCmp>& nums)
{
  if (s.length() + lb > len) return;
  if (s.length() == len && lb == 0) {
    nums.insert (s);
    return;
  }
  if (s.length() >= len) return;

  for (vector<entry::adjentry>::iterator i = n.adj.begin(); i != n.adj.end(); ++i) {
    if (i->to->count == 0) lb -= i->to->lowerbound;
    i->to->count++;
    gen_numbers (len, s+i->add, puz, lb, *(i->to), nums);
    i->to->count--;
    if (i->to->count == 0) lb += i->to->lowerbound;
  }
  for (vector<entry>::iterator i = puz.begin(); i != puz.end(); ++i) {
    if (i->count == 0) lb -= i->lowerbound;
    i->count++;
    gen_numbers (len, s+i->val, puz, lb, *i, nums);
    i->count--;
    if (i->count == 0) lb += i->lowerbound;
  }
}

void gen_numbers (size_t len, const string& s, vector<entry>& puz, size_t& lb,
		  set<string,NumberCmp>& nums)
{
  if (s.length() + lb > len) return;
  if (s.length() == len && lb == 0) {
    nums.insert (s);
    return;
  }
  if (s.length() >= len) return;

  for (vector<entry>::iterator i = puz.begin(); i != puz.end(); ++i) {
    if (s.length() == 0 && i->val == "0") continue;
    if (i->count == 0) lb -= i->lowerbound;
    i->count++;
    gen_numbers (len, s+i->val, puz, lb, *i, nums);
    i->count--;
    if (i->count == 0) lb += i->lowerbound;
  }
}

void read_generators (istream& is, map<string, set<string> >& generators)
{
  string buf;

  while (getline (is, buf)) {
    istringstream iss(buf);
    string src;
    iss >> src;
    string gen;
    while (iss >> gen) {
      generators[src].insert(gen);
    }
  }
}

void add_to_closure (map<string, set<string> >& generators,
		  const string& s, set<string>& closure)
{
  if (closure.find (s) != closure.end()) return;
  closure.insert (s);

  for (size_t i=0; i<s.length(); ++i) {
    string digit (s, i, 1);
    add_to_closure (generators, digit, closure);
    if (generators.find (digit) == generators.end()) continue;
    for (set<string>::iterator j = generators[digit].begin();
	 j != generators[digit].end(); ++j) {
      add_to_closure (generators, *j, closure);
    }
  }
}

void collect_valsets (set<set<string> >& valsets,
		      map<string, set<string> >& generators,
		      map<string, set<string> >::iterator cur, 
		      set<string>& curset)
{
  if (cur == generators.end()) {
    if (curset.size() > 0) {
      set<string> closure;
      for (set<string>::iterator i = curset.begin(); i != curset.end(); ++i) {
	add_to_closure (generators, *i, closure);
      }
      valsets.insert (closure);
    }
  } else {
    const string& s = cur->first;
    ++cur;
    collect_valsets (valsets, generators, cur, curset);
    curset.insert (s);
    collect_valsets (valsets, generators, cur, curset);
    curset.erase (s);
  }
}

int main (int ac, char **av)
{
  map<string, set<string> > generators;

  if (ac > 1) {
    ifstream is (av[1]);
    read_generators (is, generators);
  } else {
    read_generators (cin, generators);
  }

#if 0
  cout << "generators:" << endl;
  for (map<string, set<string> >::iterator i = generators.begin(); i != generators.end(); ++i) {
    cout << i->first << ":";
    for (set<string>::iterator j = i->second.begin(); j != i->second.end(); ++j) {
      cout << " " << *j;
    }
    cout << endl;
  }
#endif

  set<set<string> > valsets;
  set<string> valset;
  collect_valsets (valsets, generators, generators.begin(), valset);

#if 0
  cout << "string sets:" << endl;
  for (set<set<string> >::iterator i = valsets.begin(); i != valsets.end(); ++i) {
    for (set<string>::iterator j = i->begin(); j != i->end(); ++j) {
      cout << *j << " ";
    }
    cout << endl;
  }
#endif

  vector<entryset> entrysets (valsets.size());
  {
    vector<entryset>::iterator j = entrysets.begin();
    for (set<set<string> >::iterator i = valsets.begin(); i != valsets.end(); ++i) {
      prep_entries (*i, j->entries, j->tot_lowerbound);
#if 0
      for (vector<entry>::iterator k = j->entries.begin(); k != j->entries.end(); ++k) {
	cout << k->val << ": lb " << k->lowerbound << " (" << k->count << "):";
	for (vector<entry::adjentry>::iterator l = k->adj.begin(); l != k->adj.end(); ++l) {
	  cout << " +" << l->add << "=" << l->to->val;
	}
	cout << endl;
      }
      cout << "lowerbound: " << j->tot_lowerbound << endl;
      cout << endl;
#endif
      ++j;
    }
  }

  size_t len = 1;
  for (;;) {
    set<string,NumberCmp> nums;
    for (vector<entryset>::iterator i = entrysets.begin(); i != entrysets.end(); ++i) {
      string s = "";
      gen_numbers (len, s, i->entries, i->tot_lowerbound, nums);
    }
    for (set<string,NumberCmp>::iterator i = nums.begin(); i != nums.end(); ++i) {
      cout << *i << endl;
    }
    ++len;
  }
}