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

static char VERSION_STRING[]="B-Tree v1.2.5  08/12/1995";

#undef DEBUG

/*
void illeszt(KTYP kulcs);
DTYP keres(KTYP kulcs, LPTR reszfa);            // Visszaadja az adott kulcsb˘l meglev“ darabsz mot.
EPTR kicsi(LPTR reszfa);                        // A legkisebb elem cˇme
EPTR nagy(LPTR reszfa);                         // A legnagyobb elem cˇme
void bejar(LPTR reszfa)                         // Sorban kiˇrja az elemeket ‚s azok darabsz m t
int megkeres(LPTR akt, VPTR last, boolean *siker) // Megkeresi, hogy az "akt" lapnak hanyadik kulcsa a "last". -1 -> p0
*/

#define N 2
#define NN 2*N
#define boolean int
#define TRUE 1
#define FALSE 0
#define ERROR -1

typedef char NTYP;
typedef void *VPTR;
typedef int KTYP;
typedef int DTYP;

typedef struct strElem {
  KTYP nKulcs;
  DTYP nDarab;
  VPTR pElem;
} ELEM, *EPTR;

typedef struct strLap {
  NTYP nElem;
  VPTR p0;
  ELEM e[NN];
} LAP, *LPTR;

LPTR kezdo,qp;
KTYP kulcs;
boolean ujlapkell;
ELEM ujelem;


boolean berak(LPTR reszfa, int idx, EPTR pFel, EPTR u)
{
  int i;
  boolean bFel;
  LPTR b;

  if (reszfa->nElem<NN) {
    reszfa->nElem++;
    bFel=FALSE;
    for (i=reszfa->nElem-1; i>idx+1; i--) reszfa->e[i]=reszfa->e[i-1];
    reszfa->e[idx+1]=*u;
  }
  else {
    bFel=TRUE;
    if ((b=(LPTR)malloc(sizeof(LAP)))==NULL) return (ERROR);
    if (idx<N) {
      if (idx==N-1) *pFel=*u;
      else {
        *pFel=reszfa->e[N-1];
        for (i=N-1; i>idx+1; i--) reszfa->e[i]=reszfa->e[i-1];
        reszfa->e[idx+1]=*u;
      }
      for (i=0; i<N; i++) b->e[i]=reszfa->e[i+N];
    }
    else {
      idx-=N;
      *pFel=reszfa->e[N];
      for(i=0; i<idx; i++) b->e[i]=reszfa->e[i+N+1];
      b->e[idx]=*u;
      for(i=idx+1; i<N; i++) b->e[i]=reszfa->e[i+N];
    }
    reszfa->nElem=N;
    b->nElem=N;
    b->p0=pFel->pElem;
    pFel->pElem=b;
  }
  return(bFel);
}

void epit(KTYP kulcs, LPTR reszfa, boolean *pbFel, EPTR pFel)
{
  int idx;
  LPTR ptr;
  ELEM uelem;

  if(reszfa==NULL) {
    pFel->nKulcs=kulcs;
    pFel->pElem=NULL;
    pFel->nDarab=1;
    *pbFel=TRUE;
  }
  else {
    idx=reszfa->nElem-1;
    while(kulcs<reszfa->e[idx].nKulcs && idx>0) idx--;
    if(kulcs==reszfa->e[idx].nKulcs) {
      reszfa->e[idx].nDarab++;
#ifdef DEBUG
      printf("\n");
      printf("%6d/%02x",reszfa->e[idx].nKulcs,reszfa->e[idx].nDarab);
      printf("%6d",kulcs);
      printf("I\n");
#endif
      *pbFel=FALSE;
    }
    else {
      if (kulcs<reszfa->e[0].nKulcs) {
        idx=-1;
        ptr=(LPTR)reszfa->p0;
      }
      else ptr=(LPTR)reszfa->e[idx].pElem;
      epit(kulcs,ptr,pbFel,&uelem);
      if (*pbFel) *pbFel=berak(reszfa,idx,pFel,&uelem);
    }
  }
}

void illeszt(KTYP kulcs)
{
  epit(kulcs,kezdo,&ujlapkell,&ujelem);
  if(ujlapkell) {
    qp=kezdo;
    kezdo=(LPTR)malloc(sizeof(LAP));
    kezdo->nElem=1;
    kezdo->p0=qp;
    kezdo->e[0]=ujelem;
  }
}

DTYP keres(KTYP kulcs, LPTR reszfa)
{
  int idx;
  LPTR ptr;

  if(reszfa==NULL) return 0;
  idx=reszfa->nElem-1;
  while(kulcs<reszfa->e[idx].nKulcs && idx>0) idx--;
  if(kulcs==reszfa->e[idx].nKulcs) return reszfa->e[idx].nDarab;
  else {
    if (kulcs<reszfa->e[0].nKulcs) ptr=(LPTR)reszfa->p0;
    else ptr=(LPTR)reszfa->e[idx].pElem;
    return keres(kulcs,ptr);
  }
}

EPTR kicsi(LPTR reszfa)
{
  LPTR ptr;

  if (reszfa==NULL) return NULL;
  ptr=reszfa;
  while (ptr->p0 != NULL) ptr=(LPTR)ptr->p0;
  return &(ptr->e[0]);
}

EPTR nagy(LPTR reszfa)
{
  LPTR ptr,lastptr;

  if (reszfa==NULL) return NULL;
  ptr=reszfa;
  while (ptr->nElem) {
    lastptr=ptr;
    ptr=(LPTR)ptr->e[ptr->nElem-1].pElem;
  }
  return &(lastptr->e[lastptr->nElem-1]);
}

void bejar(LPTR reszfa)
{
  int f;

  if (reszfa==NULL) return;
  bejar((LPTR)reszfa->p0);
  for (f=0; f<reszfa->nElem; f++) {
    printf("%d/%d ",reszfa->e[f].nKulcs,reszfa->e[f].nDarab);
    bejar((LPTR)reszfa->e[f].pElem);
  }
}

int megkeres(LPTR akt, VPTR last, boolean *siker)     /* Megkeresi, hogy az "akt" lapnak
                                                         hanyadik kulcsa a "last". -1 -> p0 */
{
  int f;

  *siker=(akt->p0==last);
  for (f=-1; (f<akt->nElem-1) && !*siker; ) {
    f++;
    *siker|=(akt->e[f].pElem==last);
  }
  return f;
}

/*function kovetkezo: EPTR;
var f: ITYP;
    akt,last: LPTR;
    flag: boolean;
begin
  if aktlap=NIL then kovetkezo:=NIL
  else begin
    if (aktidx<aktlap^.nElem-1) and (aktlap^.e[aktidx].pElem=NIL) then inc(aktidx)
    else begin
      if aktlap^.e[aktidx].pElem<>NIL then kovetkezo:=legkisebb(aktlap^.e[aktidx].pElem)
      else begin
        flag:=false;
        last:=NIL;
        akt:=aktlap;
        while (akt<>NIL) and not flag do begin
          if last<>NIL then f:=megkeres(akt,last,flag);
          if not flag then begin
            last:=akt;
            akt:=akt^.up;
          end
          else if akt<>NIL then begin
            if akt^.nElem-1>f then inc(f)
            else begin
              flag:=false;
              last:=akt;
              akt:=akt^.up;
            end;
          end;
        end;
        if akt=NIL then aktlap:=NIL
        else begin
          aktlap:=akt;
          aktidx:=f;
        end;
      end;
    end;
    kovetkezo:=@(aktlap^.e[aktidx]);
  end;
end;

function elozo: EPTR;
var f: ITYP;
    akt,last: LPTR;
    flag: boolean;
begin
  if aktlap=NIL then elozo:=NIL
  else begin
    if (aktidx>0) and (aktlap^.e[aktidx].pElem=NIL) then dec(aktidx)
    else begin
      akt:=kovlap(aktlap,aktidx-1);
      if akt<>NIL then begin
        elozo:=legnagyobb(akt);
        exit;
      end
      else begin
        akt:=aktlap;
        flag:=false;
        last:=NIL;
        while (akt<>NIL) and not flag do begin
          if last<>NIL then f:=megkeres(akt,last,flag);
          if not flag then begin
            last:=akt;
            akt:=akt^.up;
          end
          else if (akt<>NIL) and (f<0) then begin
            flag:=false;
            last:=akt;
            akt:=akt^.up;
          end;
        end;
      end;
      if akt=NIL then aktlap:=NIL
      else begin
        aktlap:=akt;
        aktidx:=f;
      end;
    end;
    elozo:=@(aktlap^.e[aktidx]);
  end;
end;
*/

void bemasol(LPTR reszfa)
{
  int f;

  if (reszfa==NULL) return;
  bemasol((LPTR)reszfa->p0);
  for (f=0; f<reszfa->nElem; f++) {
    illeszt(reszfa->e[f].nKulcs);
    bemasol((LPTR)reszfa->e[f].pElem);
  }
  free(reszfa);
}

void nyomtat(LPTR p, int l)
{
  int i;
  if (p!=NULL) {
    for (i=0; i<l; i++) printf("     ");
    for (i=0; i<p->nElem; i++) printf("%6d/%02x",p->e[i].nKulcs,p->e[i].nDarab);
    printf("\n");
    nyomtat((LPTR)p->p0,l+1);
    for(i=0; i<p->nElem; i++) nyomtat((LPTR)p->e[i].pElem,l+1);
  }
}

main()
{
  int f;

  kezdo=NULL;
  for(f=0; f<10 && ujlapkell != ERROR; f++) {
    scanf("%u",&kulcs);
    illeszt(kulcs);
#ifdef DEBUG
    printf("%6d\n",kulcs);
    nyomtat(kezdo,1);
    printf("%6d\n",nagy(kezdo)->nKulcs);
#endif
  }
/*  do {
    scanf("%u",&kulcs);
    printf("%6d",keres(kulcs,kezdo));
  } while (kulcs);*/
  bejar(kezdo);
  if (ujlapkell==ERROR) printf("Elfogyott a mem˘ria.\n");
  return 0;
}