#include <stdio.h>
#include "gmp.h"

void nomem()
{
  fprintf(stderr,"fatal: out of memory");
  exit(111);
}

typedef struct zlist {
  mpz_t *m;
  unsigned int alloc;
} zlist;

void zlist_init(zlist *x)
{
  int i;

  x->alloc = 10;
  x->m = (mpz_t *) malloc(x->alloc * sizeof(mpz_t));
  if (!x->m) nomem();

  for (i = 0;i < x->alloc;++i)
    mpz_init(x->m[i]);
}

void zlist_ready(zlist *x,unsigned int pos)
{
  int newalloc;
  mpz_t *newm;
  int i;

  if (x->alloc > pos) return;
  newalloc = pos + (pos >> 2) + 1;

  newm = (mpz_t *) malloc(newalloc * sizeof(mpz_t));
  if (!newm) nomem();
  memcpy(newm,x->m,x->alloc * sizeof(mpz_t));
  for (i = x->alloc;i < newalloc;++i)
    mpz_init(newm[i]);
  free(x->m);
  x->m = newm;
  x->alloc = newalloc;
}

void product(mpz_t out,mpz_t a[],unsigned int n)
{
  mpz_t t1;
  mpz_t t2;

  if (n == 0) {
    mpz_set_ui(out,1);
    return;
  }
  if (n == 1) {
    mpz_set(out,a[0]);
    return;
  }

  mpz_init(t1);
  mpz_init(t2);
  product(t1,a,n/2);
  product(t2,a + n/2,n - n/2);
  mpz_mul(out,t1,t2);
  mpz_clear(t1);
  mpz_clear(t2);
}

#define SMALL 262144 /* power of two */
mpz_t rs[SMALL];

void reduce_small(mpz_t out[],mpz_t m[],unsigned int n,mpz_t u)
{
  int i;
  int j;
  int two;

  if (n == 0) return;

  if (n == 1) {
    mpz_mod(out[0],u,m[0]);
    return;
  }

  two = SMALL;
  while (n * 2 <= two)
    two /= 2;

  for (i = 0;i < two;++i)
    mpz_init(rs[i]);

  for (i = 1;i < two;i += 2)
    if (i < n)
      mpz_mul(rs[i],m[i - 1],m[i]);
    else if (i == n)
      mpz_set(rs[i],m[i - 1]);
    else
      mpz_set_ui(rs[i],1);

  for (j = 2;j < two;j += j)
    for (i = j;i < two;i += 2 * j)
      mpz_mul(rs[i],rs[i - j/2],rs[i + j/2]);

  mpz_mod(rs[two/2],u,rs[two/2]);

  while ((j >>= 1) >= 2)
    for (i = j;i < two;i += 2 * j) {
      mpz_mod(rs[i - j/2],rs[i],rs[i - j/2]);
      mpz_mod(rs[i + j/2],rs[i],rs[i + j/2]);
    }

  for (i = 0;i < n;++i)
    mpz_mod(out[i],rs[1 + 2 * (i/2)],m[i]);

  for (i = 0;i < two;++i)
    mpz_clear(rs[i]);
}

extern void reduce(mpz_t *,mpz_t *,unsigned int,mpz_t);
extern void reduce_clear(mpz_t *,mpz_t *,unsigned int,mpz_t);

void reduce(mpz_t out[],mpz_t m[],unsigned int n,mpz_t u)
{
  mpz_t v;

  if (n <= SMALL) {
    reduce_small(out,m,n,u);
    return;
  }

  mpz_init(v);
  product(v,m,n); /* XXX: recomputation here loses a log factor */
  mpz_mod(v,u,v);
  reduce(out,m,n/2,v);
  reduce_clear(out + n/2,m + n/2,n - n/2,v);
}

void reduce_clear(mpz_t out[],mpz_t m[],unsigned int n,mpz_t u)
{
  mpz_t v;

  if (n <= SMALL) {
    reduce_small(out,m,n,u);
    mpz_clear(u);
    return;
  }

  mpz_init(v);
  product(v,m,n);
  mpz_mod(v,u,v);
  mpz_clear(u);
  reduce(out,m,n/2,v);
  reduce_clear(out + n/2,m + n/2,n - n/2,v);
}

zlist p;
zlist q;
zlist x;
mpz_t xprod;
mpz_t n;

main()
{
  int plen;
  int xlen;
  int i;
  int j;
  int qsize;
  int xsize;

  zlist_init(&p);
  zlist_init(&q);
  zlist_init(&x);
  mpz_init(n);

  for (;;) {
    plen = 0;
    xlen = 0;

    for (;;) {
      if (!mpz_inp_str(n,stdin,10)) exit(0);
      if (mpz_sgn(n) == 0) break;
      zlist_ready(&p,plen);
      zlist_ready(&q,plen);
      mpz_set(p.m[plen],n);
      ++plen;
    }
    for (;;) {
      if (!mpz_inp_str(n,stdin,10)) exit(0);
      if (mpz_sgn(n) == 0) break;
      zlist_ready(&x,xlen);
      mpz_set(x.m[xlen],n);
      ++xlen;
    }

    mpz_init(xprod);
    product(xprod,x.m,xlen);
    reduce_clear(q.m,p.m,plen,xprod);

    qsize = 0;
    for (i = 0;i < plen;++i)
      if (!mpz_sgn(q.m[i]))
        qsize += mpz_sizeinbase(p.m[i],2);

    xsize = 0;
    for (j = 0;j < xlen;++j)
      xsize += mpz_sizeinbase(x.m[j],2);

    qsize *= 2;
    if (qsize > (xsize * 3) / 8)
      qsize = (xsize * 3) / 8;

    j = 0;
    while (j < xlen) {
      for (i = 0;i < plen;++i)
	if (!mpz_sgn(q.m[i])) {
          mpz_out_str(stdout,10,p.m[i]);
	  printf("\n");
	}
      printf("0\n");
      xsize = 0;
      while (j < xlen) {
	mpz_out_str(stdout,10,x.m[j]);
	printf("\n");
        xsize += mpz_sizeinbase(x.m[j],2);
	++j;
	if (xsize > qsize) break;
	/* XXX: need to guarantee progress for extremely unbalanced inputs */
      }
      printf("00\n");
    }
  }

  exit(0);
}