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

#define INITIAL_WORD_SIZE 10


typedef struct node {
    struct node* left;
    struct node* right;
    int counter;
    char* word;
} node;


void check_alloc(void* p) {
    if (!p) {
        printf("Out of memory!\n");
        exit(3);
    }
}

void insert(node** root, char* word) {
    if (*root == 0) {
        node* n = calloc(1,sizeof(node));
        check_alloc(n);
        n->word = word;
        n->counter = 1;
        *root = n;
        return;
    }
    // root is certainly not 0:
    node* n = *root; 
    int cmp = strcmp(n->word, word);
    if (cmp == 0) {
        ++n->counter;
        free(word);
    }
    else if (cmp > 0) {
        insert(&n->left, word);
    } 
    else { // cmp > 0
        insert(&n->right, word);
    }
}

void output(node* n) {
    if (n->left) output(n->left);
    if (n->word) printf("%s : %d\n", n->word, n->counter);
    if (n->right) output(n->right);
}

void free_nodes(node* n) {
    if (n->left) free_nodes(n->left);
    if (n->right) free_nodes(n->right);
    if (n->word) free(n->word);
    free(n);
}

int main() {
    
    node* root = 0;
    int allocated = INITIAL_WORD_SIZE + 1;
    char* word = malloc(allocated);
    check_alloc(word);
    char c;
    int len = 0;
    while ((c=getchar()) != EOF) {
        // read word
        if (isalpha(c)) {
            if (len == allocated - 1) {
                // we need more space
                allocated *= 2;
                word = realloc(word, allocated); 
                check_alloc(word);
            }
            word[len] = c; // add next letter
            ++len;
        }
        else if (len) {
            //terminate string
            word[len] = '\0';
            // insert word
            insert(&root, word);
            // reset word
            len = 0;
            allocated = INITIAL_WORD_SIZE + 1;
            word = malloc(allocated);
            check_alloc(word);
        }
    }
    
    output(root);
    
    // clean up
    free_nodes(root);
}