#include <stdio.h>
#define tmalloc(D,T,N) {D = (T *) malloc(sizeof(T)*(N)); \
  if (D==0) { fprintf(stderr,"Out of space.\n"); return(-1);}}
#define tfree(D) {if (D) free( (char *) D); D=0;}

extern char mult;
extern short wd1[],wd2[],wd3[],wd4[],
      *cst,*cend,***coeff,fullsc,clsd,lkah,conch,**cco,**def;
extern short invg[],mwdl,endr,*fpt,*bpt,nelim,lo,**imcos,dim,
       ccos,lastd,cind,nfree,stcr,endcr,fcos,bcos,lcl,np2,*rel,
       ng;

scanrel()
{ short i,j,k,l,m,necr,*s,*t; short compfsc,*p,*q,*r,esc;
  fullsc=1; stcr=endcr+2; endcr+=(1+rel[stcr-1]); esc=0;
  *wd1=0; *wd2=0; p=wd1+mwdl; q=p+dim;
  while (++p<=q) *p=0;
  p=wd2+mwdl; q=p+dim;
  while (++p<=q) *p=0;
  p=wd2+mwdl; s=rel+endcr+1; t=s+ *s; necr=endcr+ *s+1;
  while (++s<t) {p[*s]= *(s+1); s++; }
  if (mult==0 && ccos>1) action(p,def[ccos]);
  fcos=ccos; bcos=ccos; compfsc=1;
  for (i=stcr;i<=endcr;i++)
  { k=imcos[rel[i]][fcos];
    if (k==0) { compfsc=0; break;}
    if (concat(wd1,coeff[rel[i]][fcos])== -1) return(-1);
    fcos=k;
  }
  if (compfsc)
  { if (fcos!=bcos) esc=coinc(fcos,bcos);
    else if (conch) if (concheck()== -1) return(-1);
    if (esc== -1) return(-1);
    if (esc==0) endcr=necr;
    return(0);
  }
  stcr=i;
  for (i=endcr;i>=stcr;i--)
  { l=rel[i]; m=invg[l]; k=imcos[m][bcos];
    if (k==0)
    { if (i==stcr)
      { k=imcos[l][fcos];
        if (k==0)
        { imcos[l][fcos]=bcos; imcos[m][bcos]=fcos;
          if (ainvb(wd1,wd2,wd3)== -1) return(-1);
          if (*wd3>2) reduce(wd3);
          if (comp(wd3,coeff[l]+fcos)== -1) return(-1);
          invwd(wd3,wd2);
          if (comp(wd2,coeff[m]+bcos)== -1) return(-1);
        }
        else
        { if (concat(wd1,coeff[l][fcos])== -1) return(-1);
          if (k!=bcos) esc=coinc(k,bcos);
          else if (conch) if (concheck()== -1) return(-1);
          if (esc== -1) return(-1);
        }
        if (esc==0) endcr=necr;
        return(0);
      }
      if (lkah || nfree==0)
      { fullsc=0; if (esc==0) endcr=necr; return(0); }
      for (j=0;j<ng;j++) imcos[j][nfree]=0;
      cind++;
      if (mult==0)
        { tmalloc(def[nfree],short,def[bcos][0]+2);
          def[nfree][0]=def[bcos][0]+1; def[nfree][1]=l;
          for (j=1;j<=def[bcos][0];j++) def[nfree][j+1]=def[bcos][j];
        }
      imcos[m][bcos]=nfree; imcos[l][nfree]=bcos; bcos=nfree;
      bpt[nfree]=lastd; fpt[lastd]=nfree; lastd=nfree;
      nfree=fpt[nfree]; fpt[lastd]=0;
    }
    else
    { if (concat(wd2,coeff[m][bcos])== -1) return(-1); bcos=k;}
  }
  if (fcos!=bcos) esc=coinc(fcos,bcos);
  else if (conch) if (concheck()== -1) return(-1);
  if (esc== -1) return(-1);
  if (esc==0) endcr=necr;
  return(0);
}

coinc(c1,c2)  short c1,c2;
{ short lc,hc,qh,qt,i,j,y,fhc,bhc,lim,him,ret; short *ocend,esc;
  esc=0; ocend=cend; lc=1;
  while (lc!=c1 && lc!=c2) lc=fpt[lc];
  if (lc==c1) { hc=c2; ret=ainvb(wd2,wd1,wd3); }
  else { hc=c1; ret=ainvb(wd1,wd2,wd3);}
  if (ret== -1) return(-1);
  if (hc<=lo) {fprintf(stderr,"Impossible coincidence.\n"); return(-1); }
  if (compb(wd3,cco+hc)== -1) return(-1);
  qh=0; qt=0;
  fhc=fpt[hc]; bhc=bpt[hc]; fpt[bhc]=fhc;
  if (fhc==0) lastd=bhc; else bpt[fhc]=bhc;
  if (ccos==hc) { ccos=bhc; endcr=endr; esc=1; clsd=0; }
  if (lkah && lcl==hc) lcl=bhc;
  while (1)
  { fpt[hc]=nfree; nfree=hc; cind--; nelim++;
    for (i=0;i<ng;i++)
    { him=imcos[i][hc];
      if (him!=0)
      { expand(wd1,coeff[i][hc]);
        j=invg[i]; lim=imcos[i][lc];
        if (him==hc)
        { him=lc; if (concat(wd1,cco[hc])== -1) return(-1);}
        else imcos[j][him]=0;
        if (lim==0)
        { imcos[i][lc]=him;
          if (ainvb(wd3,wd1,wd2)== -1) return(-1);
          if (*wd2>2) reduce(wd2);
          if (comp(wd2,coeff[i]+lc)== -1) return(-1);
        }
        else
        { expand(wd2,coeff[i][lc]);
          if (lim==hc)
          { imcos[i][lc]=lc; lim=lc;
            if (concat(wd2,cco[hc])== -1) return(-1);
            if (*wd2>2) reduce(wd2);
            if (comp(wd2,coeff[i]+lc)== -1) return(-1);
          }
          while (fpt[him]<0)
          { if (concat(wd1,cco[him])== -1) return(-1); him= -fpt[him];}
          while (fpt[lim]<0)
          { if (concat(wd2,cco[lim])== -1) return(-1); lim= -fpt[lim];}
          if (him!=lim)
          { if (ainvb(wd3,wd1,wd4)== -1) return(-1);
            y=1;
            while (y!=him && y!=lim) y=fpt[y];
            if (y==him)
            { him=lim; lim=y; ret=ainvb(wd2,wd4,wd1); }
            else ret=ainvb(wd4,wd2,wd1);
            if (ret== -1) return(-1);
            if (him<=lo)
            { fprintf(stderr,"Impossible coincidence(q).\n"); return(-1); }
            fhc=fpt[him]; bhc=bpt[him]; fpt[bhc]=fhc;
            if (fhc==0) lastd=bhc; else bpt[fhc]=bhc;
            if (ccos==him) { ccos=bhc; endcr=endr; esc=1; clsd=0; }
            if (lkah && lcl==him) lcl=bhc;
            if (*wd1>2) reduce(wd1);
            if (compb(wd1,cco+him)== -1) return(-1);
            fpt[him]= -lim;
            if (qh==0) qh=him; else bpt[qt]=him;
            qt=him; bpt[qt]=0;
          }
        }
        y=imcos[i][lc];
        if (imcos[j][y]==0)
        { imcos[j][y]=lc; expand(wd1,coeff[i][lc]); invwd(wd1,wd2);
          if (comp(wd2,coeff[j]+y)== -1) return(-1);
        }
      }
      coeff[i][hc]=0;
    }
    if (qh==0) break;
    hc=qh; qh=bpt[qh]; lc= -fpt[hc]; bpt[hc]=0;
    expand(wd3,cco[hc]);
  }
  cend=ocend;
  return(esc);
}