>>20
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct tag_word_t{ char *word; int count; } word_t;
typedef struct tag_wordlist_t{ word_t *word; int wordnum; } wordlist_t;
int countcmp(const word_t *a, const word_t *b){return b->count - a->count;}
int wordcmp(const word_t *a, const word_t *b){return strcmp(a->word, b->word);}
void word_add(wordlist_t *wordlist, char *word){
int s, e, m, ret;
for(s = 0, e = wordlist->wordnum - 1; s <= e;){
m = (s + e) / 2;
if((ret = strcmp(wordlist->word[m].word, word)) == 0){wordlist->word[m].count += 1;return;}
if(ret < 0) s = m + 1;
else e = m - 1;
}
if((wordlist->word = realloc(wordlist->word, sizeof(word_t) * (wordlist->wordnum + 1))) == NULL) exit(1);
if((wordlist->word[wordlist->wordnum].word = strdup(word)) == NULL) exit(1);
wordlist->word[wordlist->wordnum].count = 1;
wordlist->wordnum += 1;
qsort(wordlist->word, wordlist->wordnum, sizeof(word_t), wordcmp);
}
int main(void){
wordlist_t wordlist = { NULL, 0 };
char word[256];
int i;
while(scanf("%255s", word) == 1) word_add(&wordlist, word);
qsort(wordlist.word, wordlist.wordnum, sizeof(word_t), countcmp);
for(i = 0; i < wordlist.wordnum; i++) printf("%s : %d\n", wordlist.word[i].word, wordlist.word[i].count);
return 0;
}