/* Jozef Tvarozek - Audiencia */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 10001
#define HASHN 20011

typedef struct
{
  char nam[51];
  int val,hval,num;
} HITEMF;
typedef struct
{
  char nam[51];
  int val;
} HITEMP;

FILE *fin,*fout;
int hash[HASHN];

HITEMP *pheap[HASHN];
int npheap[HASHN];
int limit[HASHN];

int tim;

HITEMF fheap[MAXN+1];
int nfheap;

int ok_hpos(int hpos, char *nam)
{
  if ( hash[hpos] == 0 )
    return 0;
  if ( strcmp(fheap[hash[hpos]].nam,nam) == 0 )
    return 0;
  return 1;
}
int get_hpos(char *nam)
{
  int i,l=strlen(nam),hpos=0;
//  printf("|%s|->",nam);
  for ( i = 0; i < l; i++)
    hpos = (hpos+3+nam[i]*47)%HASHN;
  while ( ok_hpos(hpos, nam) )
  {
    hpos++;
    if ( hpos == HASHN )
      hpos = 0;
  }
//  printf("%d\n",hpos);
  return hpos;
}
int betterf(HITEMF f1, HITEMF f2)
{
  if ( f1.num != 0 && f2.num == 0 )
    return 1;
  if ( f1.num == 0 && f2.num != 0 )
    return 0;
  if ( f1.val > f2.val )
    return 1;
  return 0;
}
int upheapf(int index)
{
  HITEMF tmp;
  int i = index;
  while ( i > 1 )
  {
    if ( betterf(fheap[i],fheap[i/2]) )
    { tmp = fheap[i]; fheap[i] = fheap[i/2]; fheap[i/2] = tmp; }
    else break;
    hash[fheap[i].hval] = i;
    hash[fheap[i/2].hval] = i/2;
    i /= 2;
  }
  return i;
}
int downheapf(int index)
{
  HITEMF tmp;
  int i=index,j;
  while ( i+i <= nfheap )
  {
    j = i+i;
    if ( j+1 <= nfheap )
      if ( betterf(fheap[j+1],fheap[j]) )
        j++;
    if ( betterf(fheap[i],fheap[j]) )
      break;
    tmp = fheap[i];
    fheap[i] = fheap[j];
    fheap[j] = tmp;
    hash[fheap[i].hval] = i;
    hash[fheap[j].hval] = j;
    i = j;
  }
}
int add_family(int hpos,char *nam, int nob)
{
  nfheap++;
  strcpy(fheap[nfheap].nam,nam);
  fheap[nfheap].val = nob;
  fheap[nfheap].hval = hpos;
  fheap[nfheap].num = 1;
  return upheapf(nfheap);
}

int add_hash(char *nam, int val)
{
  int pos = get_hpos(nam);
  if ( hash[pos] == 0 )
    hash[pos] = add_family(pos,nam,val);
  else
  {
    fheap[hash[pos]].num ++;
    if ( fheap[hash[pos]].num == 1 )
      upheapf(hash[pos]);
    if ( fheap[hash[pos]].val < val )
    {
      fheap[hash[pos]].val = val;
      upheapf(hash[pos]);
    }
  }
  return pos;
}
void upheapp(HITEMP *h, int index, int num)
{
  HITEMP tmp;
  int i = index;
  while ( i > 1 )
  {
    if ( h[i].val < h[i/2].val )
    { tmp = h[i]; h[i] = h[i/2]; h[i/2] = tmp; }
    i /= 2;
  }
}
int downheapp(HITEMP *h, int index,int num)
{
  HITEMP tmp;
  int i=index,j;
  while ( i+i <= num )
  {
    j = i+i;
    if ( j+1 <= num )
      if ( h[j+1].val < h[j].val )
        j++;
    if ( h[i].val < h[j].val )
      break;
    tmp = h[i];
    h[i] = h[j];
    h[j] = tmp;
    i = j;
  }
}
void add_nam(char *nam, int iheap)
{
  if ( limit[iheap] == 0 )
  {
    limit[iheap] = 3;
    pheap[iheap] = (HITEMP*)malloc(limit[iheap]*sizeof(HITEMP));
  }
  else
    if ( npheap[iheap]+1 == limit[iheap] )
    {
      limit[iheap] *= 2;
      pheap[iheap] = (HITEMP*)realloc(pheap[iheap],limit[iheap]*sizeof(HITEMP));
    }
  npheap[iheap]++;
  strcpy(pheap[iheap][npheap[iheap]].nam,nam);
  pheap[iheap][npheap[iheap]].val = tim;
  upheapp(pheap[iheap],npheap[iheap],npheap[iheap]);
}
void writeh(HITEMP *h, int num)
{
  int i;
  for (i = 1; i <= num; i++)
    printf("%s %d\n",h[i].nam,h[i].val);
}
void get_next(void)
{
  int i;
  if ( nfheap == 0 || fheap[1].num == 0 )
  {
//    printf("No one is waiting.\n");
    fprintf(fout,"No one is waiting.\n");
    return;
  }
  i = fheap[1].hval;
  fprintf(fout,"%s ",pheap[i][1].nam);
//  printf("%s ",pheap[i][1].nam);

  if ( npheap[i] == 1 )
    npheap[i]--;
  else
  {
    pheap[i][1] = pheap[i][npheap[i]--];
    downheapp(pheap[i],1,npheap[i]);
//    printf("*********\n");
//    writeh(pheap[i],npheap[i]);
//    getchar();
  }

//  printf("%s\n",fheap[1].nam);
  fprintf(fout,"%s\n",fheap[1].nam);
  fheap[1].num--;
  downheapf(1);
}
void writep(void)
{
  int i;
  for (i = 1; i <= nfheap; i++)
    printf("%s %d hash=%d pocet=%d\n",fheap[i].nam,fheap[i].val,fheap[i].hval,fheap[i].num);
}

int main(void)
{
  char buf[1000],nam1[100],nam2[100];
  int nob,i,j;

//   printf("-------\n");
  fin = fopen("aud.in","rt");
  fout = fopen("aud.out","wt");
  /*
  for (i = 20000; i < 21000; i++)
  {
    for (j = 2; j < i; j++)
      if ( i % j == 0)
        break;
    if ( j == i )
    {  printf("%d\n",i);

      break;
    }
  }
  */
  while ( !feof(fin) )
  {
//    printf("hash[140] = %d, hash[2564] = %d\n",hash[140],hash[2564]);
    fgets(buf,999,fin);
    buf[strlen(buf)-1] = 0;
    if ( strcmp(buf,"Bye.") == 0 )
      break;
    if ( strcmp(buf,"Next.") == 0 )
    {
      get_next();
//      writep();
//      getchar();
      continue;
    }
    sscanf(buf,"%s %s %d",nam1,nam2,&nob);
    i = add_hash(nam2,nob);
    add_nam(nam1,i);
//    printf("rodina %s\n",nam2);
//    writeh(pheap[i],npheap[i]);
//    getchar();
//    writep();
//    getchar();
    tim++;
  }
  for (i = 0; i < HASHN; i++)
    if ( limit[i] )
    {
      limit[i] = 0; npheap[i] = 0;
      free(pheap[i]);
    }
  return 0;
}
