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

typedef struct _cvor
{
        char word[80];
        int  count;
        struct _cvor *left,*right;
} cvor;

cvor* niz[50];
int size = 0;

int compare(const void *a1,const void *a2)
{
	return (*(cvor**)a1)->count - (*(cvor**)a2)->count;
}

cvor* makeNode()
{
      cvor* novi=(cvor*)malloc(sizeof(cvor));
      if(!novi)
      {
               fprintf(stderr,"Greska pri alokaciji memorije!\n");
               return NULL;
      }
      
      novi->count = 0;
      novi->left = novi->right = NULL;
	  return novi;
} 
 
void insertWord(char* s,cvor** tree)
{
     if(!(*tree))
     {
              *tree = makeNode();
              strcpy((*tree)->word,s);
              (*tree)->count = 1;
			  niz[size++]=*tree;			  
     }
     else
     {
              if(strcmp((*tree)->word,s)>0)
                  insertWord(s,&(*tree)->left);
              else if (strcmp((*tree)->word,s)<0)
                  insertWord(s,&(*tree)->right);
              else 
                   ((*tree)->count)++;
     }
}

void printTree(cvor* tree)
{
	if(!tree)
		return;
	else
	{
		printTree(tree->left);
		printf("\n%s",tree->word);
		printf(" %d",tree->count);
		printTree(tree->right);
	}
}

void clearTree(cvor* tree)
{
	if(!tree)
		return;
	else
	{
		clearTree(tree->left);
		clearTree(tree->right);
		free(tree);
	}
}
		
int main(int argc,char* argv[])
{
	int compare(const void*,const void*);
	int i;
    char word[80];
    cvor* tree = NULL;
    for(i=0;i<5;i++)
    {
        scanf("%s",word);
        insertWord(word,&tree);
    }
	printTree(tree);
	putchar('\n');
	qsort(niz,size,sizeof(cvor*),compare);
	for(i=0;i<size;i++)
		printf(" %s %d ",niz[i]->word,niz[i]->count);
	putchar('\n');
	clearTree(tree);
}