/*
 * Reads a problem from stdin and either solves it or reports it as
 *  unsolvable.
 *
 * Problem syntax:
 *
 *	B   S  s1 s2 s3 s4 ...
 *
 *	b1     x  x  x  x ...
 *	b2     x  x  x  x ...
 *	...
 *
 *  s1, s2, etc are the passenger counts of the various stops; b1, b2,
 *  etc are the passenger capacities of the various buses.  The
 *  characters represented by x in the above chart can be *, to
 *  indicate that a bus stops at a stop, or - or ., to indicate that it
 *  doesn't.
 *
 * The problem ends at EOF, or at the first completely blank line after
 *  the first bus line; the first bus line is the first nonblank line
 *  after the first line.
 *
 * Each bus line must have exactly one stops-at character for each
 *  stop, or the problem is malformed (which produces an error message
 *  and an exit).  The "B" and "S" must appear on the first line.
 *
 * Whitespace is ignored except that (a) newlines are significant and
 *  (b) whitespace serves to separate numbers which would otherwise run
 *  together on the first line.  In particular, things do not have to
 *  align as shown above;
 *
 *	BS10 20       30
 *	
 *	     15   -*-
 *	 5*    *         -
 *	45     *-        *
 *
 *  is a perfectly valid problem file, though it would more canonically
 *  be written more like
 *
 *	B  S 10 20 30
 *
 *	15    -  *  -
 *	 5    *  *  -
 *	45    *  -  *
 *
 * This program is explicitly in the public domain.
 */

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <strings.h>

extern const char *__progname;

typedef struct stop STOP;
typedef struct bus BUS;
typedef struct at AT;

struct stop {
  STOP *link;
  int i;
  unsigned int pop;
  unsigned int cur;
  AT *ats;
  } ;

struct bus {
  BUS *link;
  int i;
  unsigned int cap;
  unsigned int cur;
  AT *ats;
  } ;

struct at {
  AT *slink;
  AT *blink;
  STOP *s;
  BUS *b;
  int n;
  } ;

static STOP *stops;
static int nstops;
static BUS *buses;
static int nbuses;
static AT ***aarray;
static int sdigs;
static int bdigs;

static int digitcount(unsigned int v)
{
 int n;

 for (n=1;v>10;n++,v/=10) ;
 return(n);
}

static void load_problem(void)
{
 char *bb;
 int ba;
 int bl;
 int bi;
 STOP *s;
 STOP **st;
 BUS *b;
 BUS **bt;
 AT *a;
 char *ep;
 long int vul;
 int vui;
 int i;
 STOP *maxs;
 BUS *maxb;

 int read_line(void)
  { int c;
    void savec(int ch)
     { if (bl >= ba) bb = realloc(bb,ba=bl+8);
       bb[bl++] = ch;
     }
    bl = 0;
    while (1)
     { c = getchar();
       if (c == EOF)
	{ if (bl > 0)
	   { fprintf(stderr,"%s: missing newline at EOF - truncated?\n",__progname);
	     exit(1);
	   }
	  return(0);
	}
       if (c == '\n')
	{ savec('\0');
	  bl --;
	  return(1);
	}
       savec(c);
     }
  }

 void skipws(void)
  { while ((bi < bl) && isspace((unsigned char)bb[bi])) bi ++;
  }

 char nonwsc(void)
  { skipws();
    return(bb[bi++]);
  }

 bb = 0;
 ba = 0;
 bl = 0;
 if (! read_line())
  { fprintf(stderr,"%s: empty input\n",__progname);
    exit(1);
  }
 bi = 0;
 if ( (nonwsc() != 'B') ||
      (nonwsc() != 'S') )
  { fprintf(stderr,"%s: bad leadin\n",__progname);
    exit(1);
  }
 st = &stops;
 while (1)
  { skipws();
    if (! bb[bi]) break;
    vul = strtoul(bb+bi,&ep,0);
    if (ep == bb+bi)
     { fprintf(stderr,"%s: bad number in stops line at: %s\n",__progname,ep);
       exit(1);
     }
    bi = ep - bb;
    vui = vul;
    if (vui != vul)
     { fprintf(stderr,"%s: out-of-range number in stops line at: %s\n",__progname,bb+bi);
       exit(1);
     }
    s = malloc(sizeof(STOP));
    s->pop = vui;
    *st = s;
    st = &s->link;
  }
 *st = 0;
 i = 0;
 for (s=stops;s;s=s->link)
  { s->i = i++;
    s->ats = 0;
  }
 nstops = i;
 while (1)
  { if (! read_line())
     { fprintf(stderr,"%s: no bus lines\n",__progname);
       exit(1);
     }
    bi = 0;
    skipws();
    if (bb[bi]) break;
  }
 bt = &buses;
 while (1)
  { skipws();
    if (! bb[bi]) break;
    vul = strtoul(bb+bi,&ep,0);
    if (ep == bb+bi)
     { fprintf(stderr,"%s: bad number in bus line at: %s\n",__progname,ep);
       exit(1);
     }
    bi = ep - bb;
    vui = vul;
    if (vui != vul)
     { fprintf(stderr,"%s: out-of-range number in bus line at: %s\n",__progname,bb+bi);
       exit(1);
     }
    b = malloc(sizeof(BUS));
    b->cap = vui;
    *bt = b;
    bt = &b->link;
    b->ats = 0;
    for (s=stops;s;s=s->link)
     { skipws();
       switch (bb[bi])
	{ case '\0':
	     fprintf(stderr,"%s: too few stop flag characters in bus line: %s\n",__progname,bb);
	     exit(1);
	     break;
	  case '.': case '-':
	     break;
	  case '*':
	     a = malloc(sizeof(AT));
	     a->slink = s->ats;
	     s->ats = a;
	     a->blink = b->ats;
	     b->ats = a;
	     a->s = s;
	     a->b = b;
	     break;
	  default:
	     fprintf(stderr,"%s: bad stop flag character in bus line at: %s\n",__progname,bb+bi);
	     exit(1);
	     break;
	}
       bi ++;
     }
    skipws();
    if (bb[bi])
     { fprintf(stderr,"%s: too many stop flag characters in bus line: %s\n",__progname,bb);
       exit(1);
     }
    if (! read_line()) break;
    bi = 0;
  }
 *bt = 0;
 i = 0;
 for (b=buses;b;b=b->link) b->i = i++;
 nbuses = i;
 free(bb);
 aarray = malloc(nstops*sizeof(AT **));
 aarray[0] = malloc(nstops*nbuses*sizeof(AT *));
 for (i=(nstops*nbuses)-1;i>=0;i--) aarray[0][i] = 0;
 for (i=1;i<nstops;i++) aarray[i] = aarray[i-1] + nbuses;
 for (s=stops;s;s=s->link) for (a=s->ats;a;a=a->slink) aarray[s->i][a->b->i] = a;
 maxs = 0;
 for (s=stops;s;s=s->link) if (!maxs || (s->pop > maxs->pop)) maxs = s;
 maxb = 0;
 for (b=buses;b;b=b->link) if (!maxb || (b->cap > maxb->cap)) maxb = b;
 sdigs = digitcount(maxs->pop);
 bdigs = digitcount(maxb->cap);
}

static void dump_problem(void)
{
 STOP *s;
 BUS *b;
 AT *a;
 char sflag[nstops];

 printf("B%*sS",bdigs,"");
 for (s=stops;s;s=s->link) printf(" %*d",sdigs,s->pop);
 printf("\n\n");
 for (b=buses;b;b=b->link)
  { printf("%*d  ",bdigs,b->cap);
    bzero(&sflag[0],nstops);
    for (a=b->ats;a;a=a->blink) sflag[a->s->i] = 1;
    for (s=stops;s;s=s->link) printf(" %*s",sdigs,sflag[s->i]?"*":"-");
    printf("\n");
  }
}

static void check_seth(void)
{
 STOP *s;
 int i;
 AT *a;
 BUS *b;
 unsigned int ssum;
 unsigned int bsum;
 char counter[nstops];
 char busvec[nbuses];

 bzero(&counter[0],nstops);
 while (1)
  { for (i=nstops-1;(i>=0)&&counter[i];i--) counter[i] = 0;
    if (i < 0) break;
    counter[i] = 1;
    bzero(&busvec[0],nbuses);
    ssum = 0;
    for (s=stops;s;s=s->link)
     { if (! counter[s->i]) continue;
       ssum += s->pop;
       for (a=s->ats;a;a=a->slink) busvec[a->b->i] = 1;
     }
    bsum = 0;
    for (b=buses;b;b=b->link) if (busvec[b->i]) bsum += b->cap;
    if (ssum > bsum)
     { printf("Seth's test failed.\n");
       printf("Stops:");
       for (s=stops;s;s=s->link)
	{ if (counter[s->i])
	   { printf(" %d(%d)",s->i,s->pop);
	   }
	}
       printf(" = %d\n",ssum);
       printf("Buses:");
       for (b=buses;b;b=b->link)
	{ if (busvec[b->i])
	   { printf(" %d(%d)",b->i,b->cap);
	   }
	}
       printf(" = %d\n",bsum);
       exit(0);
     }
  }
}

static void solve_setup(void)
{
 STOP *s;
 BUS *b;
 AT *a;

 for (s=stops;s;s=s->link) s->cur = 0;
 for (b=buses;b;b=b->link)
  { b->cur = 0;
    for (a=b->ats;a;a=a->blink) a->n = 0;
  }
}

static void dump_state(void)
{
 STOP *s;
 BUS *b;
 AT *a;
 AT *sa[nstops];
 int i;

 printf("\nB%*sS",(bdigs*2)+1,"");
 for (s=stops;s;s=s->link) printf(" %*d/%*d",sdigs,s->cur,sdigs,s->pop);
 printf("\n\n");
 for (b=buses;b;b=b->link)
  { printf("%*d/%*d  ",bdigs,b->cur,bdigs,b->cap);
    for (i=nstops-1;i>=0;i--) sa[i] = 0;
    for (a=b->ats;a;a=a->blink) sa[a->s->i] = a;
    for (s=stops;s;s=s->link)
     { if (sa[s->i])
	{ printf(" %*d%*s",sdigs+1,sa[s->i]->n,sdigs,"");
	}
       else
	{ printf(" %*s%*s",sdigs+1,"-",sdigs,"");
	}
     }
    printf("\n");
  }
 printf("\n");
}

static void add_one_passenger(STOP *s)
{
 __label__ done;

 AT *a;
 AT *a2;
 BUS *b;
 char ss[nstops];
 STOP *ssparent[nstops];
 BUS *sspbus[nstops];

 void add_to_ss(STOP *s, STOP *sp, BUS *bp)
  { AT *a;
    printf("adding %d(%d/%d) to SS, ",s->i,s->cur,s->pop);
    if (sp)
     { printf("parent %d(%d/%d) via %d(%d/%d)\n",
	sp->i,sp->cur,sp->pop,bp->i,bp->cur,bp->cap);
     }
    else
     { printf("root\n");
     }
    ss[s->i] = 1;
    ssparent[s->i] = sp;
    sspbus[s->i] = bp;
    for (a=s->ats;a;a=a->slink)
     { if (a->b->cur < a->b->cap)
	{ printf("bus %d is non-full (%d/%d)\n",a->b->i,a->b->cur,a->b->cap);
	  a->b->cur ++;
	  a->n ++;
	  while (ssparent[s->i])
	   { b = sspbus[s->i];
	     aarray[s->i][b->i]->n --;
	     s = ssparent[s->i];
	     aarray[s->i][b->i]->n ++;
	     printf("chained to %d(%d/%d) via %d(%d/%d)\n",
			s->i,s->cur,s->pop,b->i,b->cur,b->cap);
	   }
	  goto done;
	}
     }
  }

 s->cur ++;
 bzero(&ss[0],nstops);
 add_to_ss(s,0,0);
 while <"ss"> (1)
  { printf("SS =");
    for (s=stops;s;s=s->link)
     { if (ss[s->i]) printf(" %d(%d/%d)",s->i,s->cur,s->pop);
     }
    printf("\n");
    for (s=stops;s;s=s->link)
     { if (ss[s->i]) continue;
       for (a=s->ats;a;a=a->slink)
	{ if (a->n > 0)
	   { for (a2=a->b->ats;a2;a2=a2->blink)
	      { if (ss[a2->s->i])
		 { add_to_ss(s,a2->s,a->b);
		   continue <"ss">;
		 }
	      }
	   }
	}
     }
    printf("impossible failure\n");
    exit(0);
  }
done:;
}

static void solve_it(void)
{
 STOP *s;

 for (s=stops;s;s=s->link)
  { while (s->cur < s->pop)
     { dump_state();
       add_one_passenger(s);
     }
  }
 dump_state();
}

int main(void);
int main(void)
{
 load_problem();
 dump_problem();
 check_seth();
 solve_setup();
 solve_it();
 exit(0);
}