// Nick Cash
// CS II - 810:062
// Assignment 2

#include <iostream>
#include <ctype.h>

using namespace std;

// to make life easier
#define LINK(m,N)   ((m) == -1 ? (N)->left : (N)->right)

// struct to store everything
struct WT
{
  string word;
  int    count;
  short  balance;
  
  WT *left;
  WT *right;
};

// function prototypes
int         lc( const string& word, string& word2 );
void        tabadd(const string& word);
void        print_tree(WT *node );
WT *        create_node( const string& word );
bool        balance(WT *tree);

//global's
WT *root = NULL; // root node

int main()
{
  string word, word2;
  
  // loop while we have input
  while ( cin )
  {
    // reset strings
    word = "";
    word2 = "";

    cin >> word;
    
    // convert to lowercase and check length
    if ( lc(word,word2) < 4 )
     continue;
     
    tabadd(word2);
  }

  // display all words recursively here?
  print_tree(root);
  cout << endl << endl;

  return EXIT_SUCCESS;
}

void tabadd( const string& word )
{
  int result = 0, a = 0;
  
  // these corrospond exactly with the variables used in the text
  WT *t = NULL, *s = NULL, *p = NULL, *q = NULL, *r = NULL, *z = NULL;
  
  // summary
  // t = parent of s
  // s = point where rebalancing may need to be done
  // p = move down the tree, normal util ptr
  // q = current node (p is a parent of q)
  // r = used later during rebalancing
  // z = my own ptr to avoid a few errors
  
  // initialize
  t = s = root;
  
  // go through tree if we have a root
  if (root != NULL )
  {
      for ( p = root; p != NULL; )
      {
         if ( p == NULL )
          return;

         // did we find our node?
         if ( (result = strcmp(word.c_str(),p->word.c_str())) == 0 )
         {
            p->count++;
            return;
         }
         else if ( result < 0 ) //left
           q = p->left;
         else                   //right
           q = p->right;


         // check to see if we need to create
         if ( q == NULL )
         {
           q = create_node( word ); // alloc and set default values

           if ( result < 0 ) // left
            p->left = q;
           else              // right
            p->right = q;

           //A6 - adjust balancing factors
           if ( strcmp(word.c_str(),s->word.c_str()) < 0)
            r = p = s->left;
           else
            r = p = s->right;

           // do this until p == q
           while ( p != q )
           {
             if ( (result = strcmp(word.c_str(),p->word.c_str())) < 0 )
             {
              p->balance = -1;
              p = p->left;
             }
             else if ( result > 0 )
             {
              p->balance = 1;
              p = p->right;
             }
             else // result == 0, p == q
              break;
           }
           // end A6

           // A7 - balancing act
           if ( strcmp(word.c_str(),s->word.c_str()) < 0 )
            a = -1;
           else
            a = 1;

           // case i
           if ( s->balance == 0 )
           {
            s->balance = a;
            root->balance++;
            return;
           }

           // case ii
           if ( s->balance == -a )
           {
             s->balance = 0;
             return;
           }

           // case iii
           if ( s->balance == a )
           {
             if ( r->balance == a ) // single rotation
             {
              // a8
              p = r;
              LINK(a,s) = LINK(-a,r);
              LINK(-a,r) = s;
              s->balance = r->balance = 0;
             }
             else if ( r->balance == -a )
             {
              // a9
              p = LINK(-a,r);
              LINK(-a,r) = LINK(a,p);
              LINK(a,p) = r;
              LINK(a,s) = LINK(-a,p);
              LINK(-a,p) = s;

              if ( p->balance == -a )
              {
               s->balance = 0;
               r->balance = a;
              }
              else if ( p->balance == 0 )
              {
               s->balance = 0;
               r->balance = 0;
              }
              else if ( p->balance == a )
              {
               s->balance = -a;
               r->balance = 0;
              }

              p->balance = 0;
             }

             //a10
             if ( s == t->right )
              t->right = p;
             else
              t->left = p;

             return;
           }
         }
         else if ( q->balance != 0 )
         {
           t = p;
           s = q;
         }

         // advance p down
         p = q;
      } // end for
  }
  else // root is null, create it
    root = create_node( word );
}

// alloc node, initialize, return
WT* create_node( const string& word )
{
  WT* node = new WT;
  
  // better safe than sorry
  if ( node == NULL )
  {
    cout << "\nOut of Memory!\n";
    abort();
  }
  
  node->left = NULL;
  node->right = NULL;
  
  node->word = word;
  
  node->balance = 0;
  node->count = 1;
  
  return node;
}

// convert the word to lowercase, return length of final string
int lc( const string& word, string& word2 )
{
  string::const_iterator end = word.end();

  // make sure word2 is clean
  word2 = "";

  // loop through word
  for ( string::const_iterator i = word.begin(); i != end; i++ )
  {
    if ( ispunct(*i) )
     continue;

    word2 += tolower(*i);
  }

  return word2.length();
}

//recursive print function
void print_tree(WT *node)
{
  if ( node )
  {
    print_tree(node->left);
    
    cout << endl << node->word << " " << node->count;
    
    print_tree(node->right);
  }
}


/////// original tabadd function /////////

// either update the count of a word or add it
//void tabadd( const string& word )
//{
//  WT *parent = NULL, *ptr;
//  int result = 0;
//
//  // find and update or find spot to add
//  for( ptr = root; ptr != NULL; )
//  {
//    // check if its the same string, store the result for analysis
//    if ( (result = strcmp(word.c_str(),ptr->word.c_str())) == 0 )
//    {
//      ptr->count++;
//      return; // exit
//    }
//
//    // store node before moving it
//    parent = ptr;
//
//    if ( result < 0 ) // to the left
//     ptr = ptr->left;
//    else
//     ptr = ptr->right;
//
//    if ( ptr == NULL ) // must insert
//     break;
//  }
//
//  //if we are here we didnt find it and it must be added
//  if ( root == NULL ) // first node?
//  {
//    root = create_node( word );
//    return;
//  }
//
//  //twasn't the root, must hang it off a parent
//  if ( result < 0 ) // left
//  {
//    ptr = create_node( word );
//    parent->left = ptr;
//  }
//  else // right
//  {
//    ptr = create_node( word );
//    parent->right = ptr;
//  }
//}