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

#define FALSE 0

typedef struct n {
    char *str;
    int cnt;
    struct n *left;
    struct n *right;
} node;

int search(node *no, char *str);
node *insert(node *no, char *str);
void deletes(node *no, char *str);
void print(node *no);
void tolist(node *no);
int cmp (const void *a, const void * b);
void clear(node *no);

node list[10101];
int indexs = 0;

int main() {
    char *str = malloc(10101 * sizeof(char));
    node *tree = NULL;
    while(fgets(str, 10101, stdin)) {
        str[strlen(str) - 1] = str[strlen(str) - 1] == '\n' ? '\0' : '\0';
        if(str[0] == '-') {
            // DELETE
            str++;
            deletes(tree, str);
        } else {
            // INSERT
            if(search(tree, str) == FALSE) {
                tree = insert(tree, str);
            }
        }
    }
    printf("Inorder traversal:\n");
    print(tree);

    printf("\nCount sorting:\n");
    tolist(tree);
    qsort(list, indexs, sizeof(node), cmp);
    for(int i = 0; i < indexs; i++) {
        printf("%d %s\n", list[i].cnt, list[i].str);
    }

    clear(tree);
}

int search(node *no, char *str) {
    if(no == NULL) return 0;
    int c = strcmp(no->str, str);
    if(c == 0) {
        no->cnt = no->cnt + 1;
        return 1;
    }
    else if (c > 0) return search(no->left, str);
    else return search(no->right, str);
}

node *insert(node *no, char *str) {
    if(no == NULL) {
        node *news = malloc(sizeof(node));
        news->str = strdup(str);
        news->cnt = 1;
        news->left = NULL;
        news->right = NULL;
        return news;
    }
    if(strcmp(no->str, str) > 0) {
        no->left = insert(no->left, str);
    } else {
        no->right = insert(no->right, str);
    }
    return no;
}

void deletes(node *no, char *str) {
    if(no == NULL) return;
    int c = strcmp(no->str, str);
    if(c == 0) {
        no->cnt = no->cnt - 1;
        return;
    } else if(c > 0) {
        deletes(no->left, str);
    } else {
        deletes(no->right, str);
    }
}

void print(node *no) {
    if(no == NULL) return;
    print(no->left);
    printf("%d %s\n", no->cnt, no->str);
    print(no->right);
    return;
}

void tolist(node *no) {
    if(no == NULL) return;
    tolist(no->left);
    node *t = no;
    list[indexs++] = *t;
    tolist(no->right);
    return;
}

int cmp (const void *a, const void * b) {
    node *aa = (node *)a;
    node *bb = (node *)b;
    return (bb->cnt - aa->cnt);
}

void clear(node *no) {
    if(no == NULL) return;
    no->str = NULL;
    no->cnt = 0;
    clear(no->left);
    clear(no->right);
    free(no);
    return;
}