/* Program to take a list of proofs (coded representations) of linearly
   realizable vectors, verify the validity of the proofs, and
   output the resulting vectors */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* A strict upper bound on the number of variables to work with */
#if !defined(NVAR)
#define NVAR 24
#endif
/* Two to the power NVAR */
#define TWOTONVAR (1 << NVAR)



int v[TWOTONVAR];
   /* The current vector to be generated for linear realizability */
int mark[TWOTONVAR];
   /* For a particular value of k (a power of 2), the value of
      mark[i] for i <= k is initially pv[i] (pv is a permuted
      version of v) but is gradually decreased as vectors are
      selected and "used up" (actually modded out by) */
int scr[TWOTONVAR];
   /* For k as above, the value of scr[i] is initially
      pv[i+k]-pv[i] (i.e., the amount that the new random
      variable should augment the dimension of subspace i)
      but is gradually decreased as vectors are allocated
      to the new random variable */
int scr2[TWOTONVAR];
   /* Initially a saved copy of the mark[] array, but then
      is used as an array of pairs of bits.  If we are
      trying to adjoin an additional vector to the new
      random variable, scr2[i]&1 is set when it is determined
      that the additional vector must be in subspace i, and
      scr2[i]&2 is set when it is determined that the additional
      vector must not be in subspace i. */



int main()
{
   int i,j,k,m,n,jj,ii;
   int readpos;
   char buffer[50000];
      /* An input buffer for the proofs */
   int inner,outer;
      /* The program sets inner to 1 when it verifies that the current
         test vector is linearly realizable, and it sets outer to 1
         when it verifies that the test vector is linearly unrealizable */
   int printmask;
      /* If a proof includes auxiliary variables, they are marked in
         this variable so that they will not be printed */
   int modmask;
      /* If a proof includes auxiliary variables, the ones giving
         subspaces we want to collapse are marked here */
   int go_on;
      /* Indicates that we haven't reached the end of the proof */

   /* Main loop on test vectors */
   for ( ; ; ) {
      /* Read in the next vector */
      if (fgets(buffer,sizeof(buffer),stdin) == NULL) break;
      v[0] = 0;
      inner = outer = 0;
      printmask = modmask = 0;

      {
         readpos = 0;
         go_on = 1;
         for (k = 1; (k < TWOTONVAR) && go_on; k <<= 1) {
            /* Set up the mark[] and scr[] arrays to respectively
               the sizes of the subspaces from the previous random
               variables and the amount that these should be
               augmented when the new random variable is adjoined */
            for (i = 0; i < k; i++) {
               v[i+k] = mark[i] = v[i];
            }
            for ( ; ; ) {
               /* Select a value of j such that we will try to adjoin
                  a generic vector from subspace j to the new
                  random variable (checking to see that certain
                  contradictions have not yet been reached) */
               i = sscanf(buffer+readpos," %d%n",&j,&n);
               if (i != 1) {
                  go_on = 0;
                  break;
               }
               readpos += n;
               if (j < 0) {
                  if (j == -2) printmask |= k;
                  else if (j == -3) {
                     /* Remove current auxiliary variables (except for
                        collapse variables) */
                     ii = 0;
                     for (i = 0; i < 2*k; i++) {
                        if (i & printmask & ~modmask) continue;
                        v[ii] = v[i];
                        mark[ii] = mark[i];
                        ii++;
                     }
                     k = ii/2;
                     jj = 0;
                     ii = 1;
                     for (i = 1; i <= printmask; i <<= 1) {
                        if (i & modmask) jj |= ii;
                        if (!(i & printmask & ~modmask)) ii <<= 1;
                     }
                     printmask = modmask = jj;
                  } else if (j == -4) {
                     printmask |= k;
                     modmask |= k;
                  }
                  break;
               }
               if (j == 0) {
                  for (i = 0; i < k; i++) v[i+k]++;
                  continue;
               }
               jj = j/k;
               j %= k;
               if (mark[j] <= 0) {
                  printf("ERROR: vector not available\n");
                  exit(1);
               }
               for (i = 0; i < k; i++) {
                  scr2[i] = mark[i];
                  if (mark[i|j] <= mark[i]) mark[i]--; else v[i+k]++;
               }
               if (jj > 0) {
                  /* Forget the generic vector from subspace j, and
                     restore the preceding mark[] and scr[] arrays */
                  for (i = 0; i < k; i++) {
                     if (scr2[i|j] <= scr2[i]) mark[i]++; else v[i+k]--;
                  }
                  /* Try to adjoin a generic vector from the intersection
                     of subspace j and subspace jj; see whether it is
                     possible to determine whether this vector is or
                     is not in each of the other subspaces (i.e., whether
                     subspace i includes the intersection of subspaces
                     j and jj) */
                  for (i = 0; i < k; i++) {
                     /* Note: if we write <i> for subspace i, so that
                        mark[i] is dim(<i>), then
                              mark[i|i'] - mark[i]
                                 = dim(<i|i'>) - dim(<i>)
                                 = dim(<i'>) - dim(<i> intersect <i'>)
                        so to check whether
                           dim(<i>intersect<i'>) <,=,> dim(<i>intersect<i''>),
                        it suffices to check whether
                           mark[i|i']-mark[i'] >,=,< mark[i|i'']-mark[i'']. */
                     scr2[i] = 0;
                     /* Don't bother adding the null vector */
                     if (i == 0) scr2[i] |= 2;
                     /* The generic vector is in subspace i if subspace i
                        includes subspace j */
                     if (mark[i|j] == mark[i]) scr2[i] |= 1;
                     /* It's in if subspace i includes subspace jj */
                     if (mark[i|jj] == mark[i]) scr2[i] |= 1;
                     /* It's in if
                            dim(<i> intersect <j>)
                               = dim(<i> intersect <jj>)
                               = dim(<i> intersect <j|jj>)
                               = dim(<j> intersect <jj>)
                        because the first two equalities give
                           <i> intersect <j>
                              = <i> intersect <j|jj>
                              = <i> intersect <jj>
                              = <i> intersect (<j> intersect <jj>) */
                     if ((mark[j]-mark[i|j] == mark[jj]-mark[i|jj]) &&
                        (mark[j]-mark[i|j] == mark[j|jj]-mark[i|j|jj]) &&
                        (mark[i]-mark[i|j] == mark[jj]-mark[j|jj]))
                        scr2[i] |= 1;
                     /* It's in if
                            dim(<j> intersect <jj>)
                               = dim(<j> intersect <jj|i>)
                               = dim(<j> intersect <i>)
                        because these give
                           <j> intersect <jj>
                              = <j> intersect <jj|i>
                              = <j> intersect <i>
                              = <j> intersect (<jj> intersect <i>).
                        Similarly with j and jj interchanged. */
                     if ((mark[jj]-mark[j|jj] == mark[i]-mark[j|i]) &&
                        (mark[jj]-mark[j|jj] == mark[i|jj]-mark[j|i|jj]))
                        scr2[i] |= 1;
                     if ((mark[j]-mark[j|jj] == mark[i]-mark[jj|i]) &&
                        (mark[j]-mark[j|jj] == mark[i|j]-mark[j|i|jj]))
                        scr2[i] |= 1;
                     /* It's out if dim(<i> intersect <j>) <
                        dim(<jj> intersect <j>) */
                     if (mark[i|j]-mark[i] > mark[jj|j]-mark[jj])
                        scr2[i] |= 2;
                     /* It's out if dim(<i> intersect <j>) <
                        dim(<jj> intersect <j>) */
                     if (mark[i|jj]-mark[i] > mark[j|jj]-mark[j])
                        scr2[i] |= 2;
                     /* It's out if subspace i does not include
                        subspace j&jj */
                     if (mark[i|(j&jj)] > mark[i]) scr2[i] |= 2;
                     /* Note that if we have spaces U,V,W with
                        V included in U, then
                           U intersect VW = (U intersect W)V.
                        [Right-to-left inclusion is easy.  For
                        left-to-right, if u = v+w, then v is in V
                        and w = u-v is in U intersect W.]
                        So if <i> includes <j>intersect<jj>, then we
                        can't have
                           dim(<i>intersect<j>) <
                              dim(<j> intersect <(i&j)|jj>)
                        because
                           <j> intersect <(i&j)|jj>
                              = (<j> intersect <jj>)<i&j>
                        and the latter is included in <i>intersect<j>. */
                     if (mark[i|j]+mark[(i&j)|jj] > mark[j|jj]+mark[i])
                        scr2[i] |= 2;
                     /* Same with j and jj interchanged */
                     if (mark[i|jj]+mark[(i&jj)|j] > mark[j|jj]+mark[i])
                        scr2[i] |= 2;
                     /* If dim(<i>intersect<j>)=dim(<j>intersect<jj>)
                        and we have an inclusion between these two
                        subspaces, then we get
                           <i>intersect<j>=<j>intersect<jj>
                        and hence <i> includes <j>intersect<jj>.  */
                     if (mark[i|j]-mark[i] == mark[j|jj]-mark[jj]) {
                        /* Inclusion holds if <j> is included in <jj>
                           (because <j>intersect<jj> is just <j>) */
                        if (mark[j|jj] == mark[jj]) scr2[i] |= 1;
                        /* Inclusion holds if <i> is included in <jj> */
                        if (mark[i|jj] == mark[jj]) scr2[i] |= 1;
                     }
                     /* Same with j and jj interchanged */
                     if (mark[i|jj]-mark[i] == mark[j|jj]-mark[j]) {
                        if (mark[j|jj] == mark[j]) scr2[i] |= 1;
                        if (mark[j|i] == mark[j]) scr2[i] |= 1;
                     }
                     /* If <(j&~jj)|(jj&~j)> (i.e., <j^jj>) is independent
                        of <j&jj>, then we have
                           <j>intersect<jj> = (<j&~jj>intersect<jj&~j>)<j&jj>.
                        [The right-to-left inclusion is easy.  For the
                        left-to-right inclusion, if x is in
                        <j> = <(j&~jj)|(j&jj)> and in <jj> = <(jj&~j)|(j&jj)>,
                        then x = y1 + z1 = y2 + z2 with y1 in <j&~jj>,
                        y2 in <jj&~j>, and z1,z2 in <j&jj>.  By the
                        independence assumption, we must have y1=y2 and z1=z2,
                        and y1=y2 is in <j&~jj>intersect<jj&~j>,
                        so we are done.]
                        So, in this case, if we also have <j&jj> included
                        in <i>, then to get <j>intersect<jj> included in <i>
                        it suffices to have <j&~jj>intersect<jj&~j> included
                        in <i>.  */
                     if ((mark[j|jj] == mark[j&jj]+mark[j^jj]) &&
                           (mark[(j&jj)|i] == mark[i])) {
                        /* The next three are just copies of previous tests
                           with  j  and  jj  changed to  j&~jj  and  jj&~j  */
                        if (mark[(j&~jj)|i] == mark[i]) scr2[i] |= 1;
                        if (mark[(jj&~j)|i] == mark[i]) scr2[i] |= 1;
                        if ((mark[j&~jj]-mark[i|(j&~jj)] ==
                              mark[jj&~j]-mark[i|(jj&~j)]) &&
                           (mark[j&~jj]-mark[i|(j&~jj)] ==
                              mark[j^jj]-mark[i|(j^jj)]) &&
                           (mark[i]-mark[i|(j&~jj)] ==
                              mark[jj&~j]-mark[j^jj]))
                           scr2[i] |= 1;
                        /* Now repeat the previous test with  i  changed to
                           i&~(j&jj)  */
                        if ((mark[j&~jj]-mark[(i&~(j&jj))|(j&~jj)] ==
                              mark[jj&~j]-mark[(i&~(j&jj))|(jj&~j)]) &&
                           (mark[j&~jj]-mark[(i&~(j&jj))|(j&~jj)] ==
                              mark[j^jj]-mark[(i&~(j&jj))|(j^jj)]) &&
                           (mark[(i&~(j&jj))]-mark[(i&~(j&jj))|(j&~jj)] ==
                              mark[jj&~j]-mark[j^jj]))
                           scr2[i] |= 1;
                     }
                     /* Apply monotonicity conditions: if the generic vector
                        is not in subspace i and subspace ii is included in
                        subspace ii, then the generic vector is not in
                        subspace ii */
                     for (ii = 1; ii < i; ii++) {
                        if ((i & ii) == ii) {
                           scr2[i] |= scr2[ii]&1;
                           scr2[ii] |= scr2[i]&2;
                        }
                     }
                  }
                  /* Check whether the determination succeeded */
                  for (i = 0; i < k; i++) {
                     if ((scr2[i] == 0) || (scr2[i] == 3)) {
                        break;
                     }
                  }
                  if (i < k) {
                     printf("ERROR: invalid proof\n");
                     exit(1);
                  }
                  /* Determination succeeded -- update mark[] and scr[] */
                  for (i = 0; i < k; i++) {
                     if (scr2[i] == 1) mark[i]--; else v[i+k]++;
                  }
               }
            }
         }
         if (go_on == 0) {
            inner = 1;
         }
         k >>= 1;
      }

      for (i = 1; i < k; i++) {
         if (mark[i] != 1) continue;
         for (j = i+1; j < k; j++) {
            if (((j&i) != i) && (mark[j] == 1)) break;
         }
         if (j < k) break;
      }
      if (i == k) {
         if (inner == 0) printf("WEIRD\n"),fprintf(stderr,"WEIRD\n");
         inner = 1;
      }

      /* Check the results for this vector -- print an error message
         if there is a contradiction, and print the vector if it
         is linearly realizable */
      if (inner) {
         j = k;
         for (k = 0; k < j; k++) {
            if (k & printmask) continue;
            /* if (k > 1) */ printf(" ");
            printf("%d",v[k | modmask] - v[modmask] /*," *x"[mark[k]]*/ );
         }
         printf("\n");
      } else {
         printf("ERROR\n");
         fprintf(stderr,"ERROR\n");
         exit(1);
      }
   }
}