//  ttt.cc -- Generate reachable tic-tac-toe games
//
//  Author: Fred Curtis (fred@f2.org)
//  Written: 2002/09/19 - Finished n-dimensional generalization
//  For some notes on tic-tac-toe problems see: http://f2.org/maths/ttt.html
//

#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
#include <string.h>

#include <unistd.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <time.h>

static int const max_dim = 3;
static int const max_path_len = 100;

static int power(int const n, int const exp) {
  int result = 1;
  for (int i = exp; i-- > 0;) {
    result *= n;
  }
  return result;
}

static int factorial(int const n) {
  return (n < 2) ? 1 : n * factorial(n - 1);
}

class perm_loop {
  //  This permutation code is based on some beautiful non-recursive code
  //  by Phillip Paul Fuchs:
  //    http://www.geocities.com/permute_it/01example.html
private:
  int const n;
  int *p;
  int curr;
public:
  bool get_swap_indices(int &i, int &j) {
    //  Returns:
    //    false if there are no more permutations
    //    true otherwise (sets i and j to the indices to be swapped)

    if (curr >= n) {
      return false;
    }

    //  Decrement p[curr] and find index to swap with curr
    //
    i = curr;
    j = curr % 2 * --p[curr];

    //  Reset any run of zeroed p[i] and find next curr
    for (curr = 1; curr < n && !p[curr]; curr++) {
      p[curr] = curr;
    }
    return true;
  }
  void reset() {
    for(int i = 0; i < n; i++) {
      p[i] = i;
    }
    curr = 1;
  }
  perm_loop(int const _n) : n(_n), p(new int[n]) {
    reset();
  }
  ~perm_loop() {
    delete p;
  }
};

class geom {
private:
  int const _ndim;
  int const _edge_length;
  int const _npiece;
  int const _ncompressed;
  int **_transforms;
  int **_win_rows;
  int index_of(int const * coord) {
    int result = 0;
    for (int i = _ndim; i-- > 0;) {
      result = result * _edge_length + *coord++;
    }
    return result;
  }
  void coord_of(int *coord, int index) {
    for (int i = _ndim; i-- > 0;) {
      coord[i] = index % _edge_length;
      index /= _edge_length;
    }
  }
public:
  int const ndim(void) const { return _ndim; }
  int const edge_length(void) const { return _edge_length; }
  int const npiece(void) const { return _npiece; }
  int const ncompressed(void) const { return _ncompressed; }
  int const * const * transforms(void) const { return _transforms; }
  int const * const win_rows(int const piece) const {
    assert(piece >= 0 && piece < _npiece);
    return _win_rows[piece];
  }
  void compress(unsigned char *dest, char const *src) const {
    int n = _npiece;
    while (n > 0) {
      int tot = 0;
      for (int i = 5; n > 0 && i-- > 0; n--, src++) {
        switch (*src) {
	case '-':
	  tot = tot * 3;
	  break;
	case 'x':
	  tot = tot * 3 + 1;
	  break;
	case 'o':
	  tot = tot * 3 + 2;
	  break;
	default:
	  cerr << "Encountered illegal char (ascii decimal " << ((int) *src) << ")" << endl;
	  assert(*src == 'x' || *src == 'o' || *src == ' ');
	}
      }
      tot++;
      *dest++ = (unsigned char) tot;
    }
  }
  void decompress(char *dest, unsigned char *src) const {
    int n = _npiece;
    while (n > 0) {
      int tot = *src++ - 1;
      char buf[5];
      char *end = &buf[4];
      char *start = end;
      for (int i = 5; n > 0 && i-- > 0; n--, tot /= 3) {
        switch (tot % 3) {
	case 0:
	  *start-- = '-';
	  break;
	case 1:
	  *start-- = 'x';
	  break;
	case 2:
	  *start-- = 'o';
	  break;
	default:
	  cerr << "Encountered illegal char (ascii decimal " << ((int) *src) << ")" << endl;
	  assert(*src == 'x' || *src == 'o' || *src == ' ');
	}
      }
      while (++start <= end) {
        *dest++ = *start;
      }
    }
  }
  ~geom() {
    for (int **p = _transforms; *p != 0; p++) {
      delete *p;
    }
    delete _transforms;
    for (int p = 0; p < _npiece; p++) {
      delete _win_rows[p];
    }
    delete _win_rows;
  }
  geom(int const ndim, int const edge_length)
    : _ndim(ndim)
    , _edge_length(edge_length)
    , _npiece(power(edge_length, ndim))
    , _ncompressed((_npiece-1)/5+1)
  {
    int const ncorner(power(2, ndim));
    int const ndim_perm(factorial(ndim));
    int const ntransform(ncorner * ndim_perm);

    //  Seed transform list with permutations corresponding to all
    //  axis permutations and all reflections
    //
    _transforms = new int * [ntransform + 1];
    _win_rows = new int * [_npiece];
    int tindex = 0;
    perm_loop ploop(ndim);
    int *coord_perm = new int[ndim];
    for (int i = 0; i < ndim; i++) {
      coord_perm[i] = i;
    }
    int **id = new int *[_npiece];
    for (int p = _npiece; p-- > 0;) {
      id[p] = new int[ndim];
      coord_of(id[p], p);
    }

    for (;;) {
      //  Process this permutation of coord_perm array

      for (int corner = ncorner; corner-- > 0;) {
        assert(tindex < ntransform);
        int *tform = new int[_npiece];
        _transforms[tindex++] = tform;

        for (int p = _npiece; p-- > 0;) {
          int tcoord[ndim];
          for (int d = ndim; d--> 0;) {
            tcoord[d] = id[p][coord_perm[d]];
            if (corner & (1<<d)) {
              tcoord[d] = edge_length - 1 - tcoord[d];
            }
          }
          *tform++ = index_of(tcoord);
        }
      }

      //  Find next permutation of coord_perm array
      int i;
      int j;
      if (!ploop.get_swap_indices(i, j)) {
        break;
      }

      //  Swap array elements i & j
      //
      int tmp = coord_perm[j];
      coord_perm[j] = coord_perm[i];
      coord_perm[i] = tmp;
    }
    assert(tindex == ntransform);
    _transforms[tindex] = 0;

    //  Calculate position vectors to check for each board cell
    //
    int nvec = 0;
    for (int d = ndim; d-- > 0;) {
      nvec += power(3, d);
    }
    int ntestable = 0;
    for (int p = _npiece; p-- > 0;) {
      int *vec = new int [(edge_length - 1) * nvec + 1];
      _win_rows[p] = vec;

      int displace[ndim];
      for (int d = ndim; d-- > 0;) {
        displace[d] = 0;
      }
      displace[ndim - 1] = 1;

      for (int k = 0; ;) {
        //  Look for candidate cells along displacement vector
        //
        int candidate[edge_length];
        int ncand = 0;

        for (int t = 1 - edge_length; t < edge_length; t++) {
          if (t == 0) {
            continue;
          }
          int tcoord[ndim];
          int ok = 1;
          for (int d = ndim; ok && d-- > 0; ) {
            tcoord[d] = id[p][d] + t * displace[d];
            ok = (tcoord[d] >= 0 && tcoord[d] < edge_length);
          }
          if (ok) {
            assert(ncand < edge_length);
            candidate[ncand++] = index_of(tcoord);
          }
        }
        if (ncand == edge_length - 1) {
          ntestable++;
          for (; ncand-- > 0;) {
            *vec++ = candidate[ncand];
          }
        }

        //  Find next displacement vector
        //
        k++;
        int d = ndim - 1;
        while (++displace[d] > 1 && d >= 0) {
          d--;
        }
        if (d < 0) {
          assert(k == nvec);
          *vec = -1;
          break;
        }
        assert(k < nvec);
        while (++d < ndim) {
          displace[d] = -1;
        }
      }
    }
    cerr << "ntestable " << ntestable << endl;
    delete coord_perm;
    for (int p = _npiece; p-- > 0;) {
      delete id[p];
    }
    delete id;
  }
};

class mem_buf {
private:
  unsigned char *_buf;
  int _fd;
  int _sz;
  char _fname[max_path_len];
public:
  unsigned char *buf(void) {
    return _buf;
  }
  int sz (void) const {
    return _sz;
  }
  mem_buf(int sz)
    : _buf(0)
    , _fd(-1)
    , _sz(0)
  {
    if (sz > 40000000) {
      _fd = 0;
      _sz = sz;
      strcpy(_fname, "/tmp/ttt-XXXXXX");
      _fd = mkstemp(_fname);
      if (_fd < 0) {
	cerr << "Can't create temp file " << endl;
	exit(1);
      }
      lseek(_fd, sz - 1, SEEK_SET);
      write(_fd, "", 1);
      _buf = (unsigned char *) mmap(0, sz, PROT_READ | PROT_WRITE, MAP_SHARED, _fd, 0);
    } else {
      _buf = (unsigned char *) malloc(sz);
    }
    assert(_buf != 0);
  }
  ~mem_buf() {
    if (_fd >= 0) {
      munmap(_buf, _sz);
      close(_fd);
      unlink(_fname);
    } else {
      free(_buf);
    }
  }
};

class config_hash {
private:
  static int _nchildren;
  static int _maxchildren;
  int const _nquantum;
  int const _elt_size;
  int _nelt;
  int _nallocated;
  mem_buf *_membuf;
  config_hash *_child;
public:
  int nelt(void) const {
    return _nelt;
  }
  void merge_children(unsigned char const **pbuf = 0, int *psize = 0) {
    if (_child != 0) {
      _child->merge_children();
      int nsum = _nelt + _child->_nelt;
      _nallocated = nsum;
      mem_buf *new_buf = new mem_buf(_nallocated * _elt_size);

      int ncurr = _nelt;
      int nchild = _child->_nelt;
      unsigned char *bcurr = _membuf->buf();
      unsigned char *bchild = _child->_membuf->buf();
      unsigned char *bnew = new_buf->buf();
//      cerr << "merge ncurr = " << ncurr << " nchild = " << nchild << endl;
      for (int i = 0; i < nsum; i++) {
        unsigned char *smallest;
	if (ncurr == 0) {
	  smallest = bchild;
	  bchild += _elt_size;
	  nchild--;
	} else if (nchild == 0) {
	  smallest = bcurr;
	  bcurr += _elt_size;
	  ncurr--;
	} else {
	  int ret = memcmp(bcurr, bchild, _elt_size);
	  if (ret < 0) {
	    smallest = bcurr;
	    bcurr += _elt_size;
	    ncurr--;
	  } else if (ret > 0) {
	    smallest = bchild;
	    bchild += _elt_size;
	    nchild--;
	  } else {
	    smallest = 0;  // To stop compiler warning
	    assert(ret != 0);
	  }
	}
//	if (i > 0) {
//	  assert(memcmp(bnew - _elt_size, smallest, _elt_size) < 0);
//	}
	memcpy(bnew, smallest, _elt_size);
	bnew += _elt_size;
      }

      delete _membuf;
      _membuf = new_buf;
      delete _child;
      _child = 0;
      _nelt = nsum;
    }
    if (pbuf != 0) {
      if (psize != 0) {
        (*psize) = _elt_size * _nelt;
      }
      (*pbuf) = ((_membuf == 0) ? 0 : _membuf->buf());
    }
  }
  static int max_children(void) {
    return _maxchildren;
  }
  bool already_had_elt(unsigned char const *elt) {
    //  Return true if elt was already in hash
    //  Return false (and add elt) if elt was not in hash
    bool found = false;
    int insert_pos = 0;
    if (_nelt > 0) {
      //  Look for elt with binary search
      //
      unsigned char *_buf = _membuf->buf();
      assert(_membuf != 0);
      int lo = 0;
      int hi = _nelt - 1;
      while (!found) {
	int pivot = (lo + hi) / 2;
        int res = memcmp(elt, &_buf[pivot * _elt_size], _elt_size);
	if (res == 0) {
	  found = true;
	} else if (res < 0) {
	  if (pivot <= lo) {
	    insert_pos = pivot;
	    break;
	  } else {
	    hi = pivot - 1;
	  }
	} else {
	  if (pivot >= hi) {
	    insert_pos = pivot + 1;
	    break;
	  } else {
	    lo = pivot + 1;
	  }
	}
      }
    }
    if (!found) {
      //  Check children
      //
      if (_child == 0 && _nelt >= _nquantum) {
        _child = new config_hash(_elt_size);
      }
      if (_child != 0) {
        found = _child->already_had_elt(elt);
	if (!found && _child->_nelt * 7 >= _nelt) {
	  merge_children();
	}
      } else {
        if (_membuf == 0) {
	  assert(_nallocated == 0);
	  _nallocated = _nquantum;
	  _membuf = new mem_buf(_nallocated * _elt_size);
	}
	assert(_nelt < _nallocated);
	unsigned char *_buf = _membuf->buf();
	memmove(&_buf[(insert_pos+1) * _elt_size], &_buf[insert_pos * _elt_size], (_nelt - insert_pos) * _elt_size);
	memcpy(&_buf[insert_pos * _elt_size], elt, _elt_size);
	_nelt++;
      }
    }
    return found;
  }
  config_hash(int const elt_size)
    : _nquantum(100)
    , _elt_size(elt_size)
    , _nelt(0)
    , _nallocated(0)
    , _membuf(0)
    , _child(0)
  {
    if (++_nchildren > _maxchildren) {
      _maxchildren = _nchildren;
    }
  }
  ~config_hash() {
    --_nchildren;
    delete _membuf;
    delete _child;
  }
};

int config_hash::_nchildren;
int config_hash::_maxchildren;

void merge_files(int elt_size, char const *src1file, char const *src2file, ostream &outf) {
  if (strcmp(src1file, src2file) == 0) {
    cout << "Refusing to merge 2 copies of same file '" << src1file << "'" << endl;
    exit(1);
  }
  unsigned char last[elt_size];
  unsigned char curr[elt_size];
  unsigned char enc1[elt_size];
  unsigned char enc2[elt_size];

  ifstream inf1;
  inf1.open(src1file);
  if (inf1.fail()) {
    cerr << "Can't read input file '" << src1file << "'" << endl;
    exit(1);
  }
  inf1.read(enc1, elt_size);

  ifstream inf2;
  inf2.open(src2file);
  if (inf2.fail()) {
    cerr << "Can't read input file '" << src2file << "'" << endl;
    exit(1);
  }
  inf2.read(enc2, elt_size);

  for (bool first = true; ; first = false) {
    if (inf1.eof()) {
      if (inf2.eof()) {
        break;
      }
      memcpy(curr, enc2, elt_size);
      inf2.read(enc2, elt_size);
    } else if (inf2.eof()) {
      memcpy(curr, enc1, elt_size);
      inf1.read(enc1, elt_size);
    } else {
      if (memcmp(enc1, enc2, elt_size) < 0) {
	memcpy(curr, enc1, elt_size);
	inf1.read(enc1, elt_size);
      } else {
	memcpy(curr, enc2, elt_size);
	inf2.read(enc2, elt_size);
      }
    }
    if (first) {
      outf.write(curr, elt_size);
    } else {
      int ret = memcmp(last, curr, elt_size);
      assert(ret <= 0);
      if (ret < 0) {
	outf.write(curr, elt_size);
      }
    }
    memcpy(last, curr, elt_size);
  }
}

class staggered_config_hash {
private:
  int _iter;
  int _elt_size;
  int _auto_flush_count;
  config_hash *_curr_impl;
  char _file_prefix[max_path_len];
  void mkfname(char *fname, int index, int depth) const {
    sprintf(fname, "%s.%c%d", _file_prefix, depth + 'a', index);
  }
  void flush(void) {
    char fname[max_path_len];
    mkfname(fname, _iter, 0);
    {
      ofstream outf;
      outf.open(fname);
      if (outf.fail()) {
	cerr << "Can't create output file '" << fname << "'" << endl;
	exit(1);
      }
      if (_curr_impl != 0) {
	unsigned char const *mem;
	int sz;
	_curr_impl->merge_children(&mem, &sz);
	outf.write(mem, sz);
	delete _curr_impl;
	_curr_impl = 0;
      }
      outf.close();
    }

    for (int depth = 1; ;depth++) {
      int mask = (1 << depth) - 1;
      if ((_iter & mask) != mask) {
        break;
      }
      char src1[max_path_len];
      char src2[max_path_len];
      char dest[max_path_len];
      mkfname(src1, (_iter >> (depth-1))-1, depth-1);
      mkfname(src2, (_iter >> (depth-1)), depth-1);
      mkfname(dest, (_iter >> depth), depth);
      ofstream outf;
      outf.open(dest);
      if (outf.fail()) {
	cerr << "Can't create output file '" << dest << "'" << endl;
	exit(1);
      }
      time_t stime = time(0);
      cout << "merging " << src1 << " & " << src2 << " -> " << dest << endl;
      merge_files(_elt_size, src1, src2, outf);
      unlink(src1);
      unlink(src2);
      outf.close();
      cerr << "merged " << src1 << " & " << src2 << " -> " << dest << " (" << (time(0) - stime) << " secs)" << endl;
    }
    _iter++;
  }
public:
  bool already_had_elt(unsigned char const *elt) {
    if (_curr_impl == 0) {
      _curr_impl = new config_hash(_elt_size);
    }
    bool retval = _curr_impl->already_had_elt(elt);
    if (_curr_impl->nelt() >= _auto_flush_count) {
      cout << "autoflush" << endl;
      flush();
    }
    return retval;
  }
  staggered_config_hash(int const elt_size, char const *file_prefix, int auto_flush_count)
    : _iter(0)
    , _elt_size(elt_size)
    , _auto_flush_count(auto_flush_count)
    , _curr_impl(0)
  {
    strcpy(_file_prefix, file_prefix);
  }
  ~staggered_config_hash() {
    flush();
//    do {
//      flush();
//    } while ((_iter & (_iter - 1)) != 0);
  }
};

void data_filename(char *result, int ndim, int edge_length, int depth, bool done) {
  sprintf(result, "%s-%d-%d-%d", done ? "done" : "todo", ndim, edge_length, depth);
}

void compute_next_depth(bool verbose, int ndim, int edge_length, int depth) {
  geom *g = new geom(ndim, edge_length);

  //  Create output files
  //
  char fname[max_path_len];

  int const ncompressed(g->ncompressed());
  int hash_lim = 40000000/ncompressed;
  data_filename(fname, ndim, edge_length, depth + 1, false);
  staggered_config_hash todo_signatures(ncompressed, fname, hash_lim);

  data_filename(fname, ndim, edge_length, depth + 1, true);
  staggered_config_hash done_signatures(ncompressed, fname, hash_lim);

  char player;
  char other;
  if (depth % 2 == 0) {
    player = 'x';
    other = 'o';
  } else {
    player = 'o';
    other = 'x';
  }

  char *canon_sig = new char[g->npiece() + 1];
  canon_sig[g->npiece()] = '\0';

  char *tsig = new char[g->npiece() + 1];
  tsig[g->npiece()] = '\0';

  unsigned char *enc = new unsigned char[ncompressed + 1];
  enc[ncompressed] = '\0';

  char *config = new char[g->npiece() + 1];
  ifstream inf_todo;

  if (depth == 0) {
    for (int p = g->npiece(); p-- > 0;) {
      config[p] = '-';
    }
  } else {
    data_filename(fname, ndim, edge_length, depth, false);
    inf_todo.open(fname);
    if (inf_todo.fail()) {
      cerr << "Can't read input file '" << fname << "'" << endl;
      exit(1);
    }
    inf_todo.read(enc, ncompressed);
  }
  config[g->npiece()] = '\0';

  time_t stime = time(0);
  int nline = 0;
  for (;;) {
    if (depth > 0) {
      if (inf_todo.eof()) {
	break;
      }
      g->decompress(config, enc);
      config[g->npiece()] = '\0';
      if (verbose) {
        cout << "Read config: '" << config << "'" << endl;
      }
    }

    //  Process this configuration
    //
    for (int p = g->npiece(); p-- > 0;) {
      if (config[p] != '-') {
        continue;
      }
      config[p] = player;

      canon_sig[0] = '\0';
      for (int const * const *t = g->transforms(); *t != 0; t++) {
        for (int q = g->npiece(); q--> 0;) {
          tsig[q] = config[(*t)[q]];
        }
        if (canon_sig[0] == '\0' || strcmp(canon_sig, tsig) > 0) {
          strcpy(canon_sig, tsig);
        }
      }

      bool won = false;
      for (int const *win_row = g->win_rows(p); !won && *win_row >= 0; ) {
	bool won_this_row = true;
	for (int r = edge_length - 1; r-- > 0; win_row++) {
	  won_this_row = won_this_row && (config[*win_row] == player);
	}
	won = won_this_row;
      }

      staggered_config_hash *sigs = 0;
      if (won) {
	sigs = &done_signatures;
      } else {
	sigs = &todo_signatures;
      }

      if (sigs != 0) {
	g->compress(enc, canon_sig);
        if (!sigs->already_had_elt(enc)) {
	  if (verbose) {
	    if (sigs == &done_signatures) {
//	    if (sigs == 0) {
	      cout << " win config: '" << config << "'" << endl;
	    } else {
	      cout << "nwin config: '" << config << "'" << endl;
	    }
	    cout << "        sig: '" << canon_sig << "'" << endl;
	  }
	}
      }

      config[p] = '-';
    }

    if (++nline % 100000 == 0) {
      cout << nline << " lines processed" << endl;
      int fd = open("status", O_RDWR | O_CREAT | O_TRUNC, 0666);
      if (fd >= 0) {
	char buf[100];
	sprintf(buf, "%d lines processed %ld sec\n", nline, (long) (time(0) - stime));
	write(fd, buf, strlen(buf));
        close(fd);
      }
    }
    //  Get next configuration
    //
    if (depth == 0) {
      break;
    }
    inf_todo.read(enc, ncompressed);
  }
  if (depth > 0) {
    inf_todo.close();
  }
  cout << "Max children = " << config_hash::max_children() << endl;
  delete canon_sig;
  delete tsig;
  delete enc;
  delete config;
}

void decode_stdin(int ndim, int edge_length) {
  geom *g = new geom(ndim, edge_length);

  unsigned char *enc = new unsigned char[g->ncompressed()];
  char *config = new char[g->npiece() + 1];
  cin.read(enc, g->ncompressed());
  while (!cin.eof()) {
    g->decompress(config, enc);
    config[g->npiece()] = '\0';
    cout << config << endl;
    cin.read(enc, g->ncompressed());
  }
  delete config;
  delete enc;
}

bool str_has_suffix(char const *universe, char const *suffix) {
  int ulen = strlen(universe);
  int slen = strlen(suffix);
  return (ulen >= slen && strcmp(universe + ulen - slen, suffix) == 0);
}

void check_ndim(int ndim) {
  if (ndim < 2 || ndim > max_dim) {
    cerr << "<ndim> param should be between 2 and " << max_dim << endl;
    exit(1);
  }
}

void check_edge_length(int edge_length) {
  if (edge_length < 3) {
    cerr << "<edge_length> param should be 3 or more" << endl;
    exit(1);
  }
}

int main(int argc, char *argv[]) {
  bool verbose = false;
  char *progname = *argv++;
  argc--;
  if (argc > 0 && strcmp(*argv, "-v") == 0) {
    verbose = true;
    argv++;
    argc--;
  }

  if (str_has_suffix(progname, "ttt")) {
    if (argc != 3) {
      cerr << "Usage: " << progname << " [-v] <ndim> <edge_length> <depth>" << endl;
      return 1;
    }
    int ndim = atoi(argv[0]);
    int edge_length = atoi(argv[1]);
    int depth = atoi(argv[2]);
    check_ndim(ndim);
    check_edge_length(edge_length);
    compute_next_depth(verbose, ndim, edge_length, depth);
  } else if (str_has_suffix(progname, "ttt-decode")) {
    if (argc != 2) {
      cerr << "Usage: " << progname << " [-v] <ndim> <edge_length>" << endl;
      return 1;
    }
    int ndim = atoi(argv[0]);
    int edge_length = atoi(argv[1]);
    check_ndim(ndim);
    check_edge_length(edge_length);
    decode_stdin(ndim, edge_length);
  } else if (str_has_suffix(progname, "ttt-merge")) {
    if (argc != 4) {
      cerr << "Usage: " << progname << " [-v] <ndim> <edge_length> <dest> <src>" << endl;
      return 1;
    }
    int ndim = atoi(argv[0]);
    int edge_length = atoi(argv[1]);
    char *src1file = argv[2];
    char *src2file = argv[3];
    check_ndim(ndim);
    check_edge_length(edge_length);
    geom *g = new geom(ndim, edge_length);
    merge_files(g->ncompressed(), src1file, src2file, cout);
  } else {
    cerr << "Don't know what to do when I'm called '" << progname << "'" << endl;
    exit(1);
  }
  return 0;
}