/**
 * K&R's tree code from 6.5, transcribed by K. Spasaro and updated by S.
 * Rebelsky.
 */

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

#define MAXWORD 100

//=============================
// struct tnode
//=============================

struct tnode 
{
  char *word;
  int count;
  struct tnode *left;
  struct tnode *right;
};

//=============================
// struct tnode *talloc
//   Rewritten b/c K&R assume that malloc sets everything to 0.
//=============================

struct tnode *talloc (void)
{
  struct tnode *node = (struct tnode *) malloc (sizeof (struct tnode));
  node->word = NULL;
  node->count = 0;
  node->left = NULL;
  node->right = NULL;
  return node;
}


//=============================
// struct tnode *addtree
//=============================

struct tnode *talloc (void);

struct tnode *addtree (struct tnode *p, char *w)
{
  int cond;
  
  if (p == NULL)
  {
    p = talloc ();
	p->word = strdup (w);
	p->count = 1;
	p-> left = p-> right = NULL;
  }
  else if ((cond = strcmp (w, p-> word)) == 0)
    p-> count++;
  else if (cond < 0)
    p-> left = addtree (p-> left, w);
  else if (cond > 0)
    p-> right = addtree (p-> right, w);
  return p;
}

//=============================
// treeprint
//=============================

void
treeprint (struct tnode *p)
{
  if (p != NULL)
  {
    treeprint (p-> left);
	printf ("%4d %s\n", p-> count, p-> word);
	treeprint (p-> right);
  }
}

//=============================
// main
//=============================

//struct tnode *addtree (struct tnode *, char *);
//void treeprint( struct tnode *);
//int getword (char *, int);

int
main ()
{
  struct tnode *root = NULL;
  char word[MAXWORD];
  
  while (fgets (word, MAXWORD-1, stdin) != NULL)
  {
    if (isalpha (word[0]))
	  root = addtree (root, word);
  }
  
  treeprint (root);
  return 0;
}