#include <stdio.h>
#include <stdlib.h>
#include <string.h>
FILE *f, *g;
typedef struct element{
    int endw, NrOfNodes;
    short int poz[27];
    struct element *next[27];
}Trie;

Trie* CreateNod() {
    Trie* p = calloc(1, sizeof(Trie));
    p->endw = p->NrOfNodes = 0;
    for(int i = 0; i < 27; ++i) {
         p->next[i] = NULL;
         p->poz[i] = 0;
    }
    return p;
}

void AddTrie(Trie** root, char* cuv) {
    if(*root == NULL)
        *root = CreateNod();
    int lengh = strlen(cuv) - 1;
    char c;
    Trie *last, *p = *root;
    for(int i = 0; cuv[i] != '\0'; ++i) {
        c = cuv[i] - 'a';
        if(!p->poz[c]) {
            p->poz[c] = 1;
            p->next[c] = CreateNod();
            ++(p->NrOfNodes);
        }
        last = p = p->next[c];
    }
    ++(last->endw);
}

void DeleteTrie(Trie** root, char* cuv) {
    if(*root == NULL)
        return;
    int lengh = strlen(cuv) - 1, m = -1;
    Trie* last, *queue[lengh + 2], *prev1 = NULL, *prev2 = NULL, *p = (*root);
    char c1, c2, c;
    for(int i = 0; cuv[i] != '\0'; ++i) {
        c = cuv[i] - 'a';
        if(!p->poz[c])
            return;
        if(p->NrOfNodes == 1)
            queue[++m] = p;
        else
            m = -1, prev1 = p, c1 = cuv[i];
        prev2 = p, c2 = cuv[i];
        last = p = p->next[c];
    }
    if(!last->NrOfNodes && last->endw == 1) {
        free(last);
        last = NULL;
        --(prev2->NrOfNodes);
        prev2->poz[c2 - 'a'] = 0;
        for(int i = 0; i <= m; ++i) {
            if(queue[i] == *root)
                *root = NULL;
            free(queue[i]);
        }
        if(m != -1 && prev1 != NULL) {
            prev1->poz[c1 - 'a'] = 0;
            --(prev1->NrOfNodes);
        }
        return;
    }
    --(p->endw);
}

int PrintFreg(Trie* root, char* cuv) {
    if(root == NULL)
        return 0;
    int lengh = strlen(cuv) - 1;
    Trie* last;
    char c;
    for(int i = 0; cuv[i] != '\0'; ++i) {
        c = cuv[i] - 'a';
        if(!root->poz[c])
            return;
        last = root = root->next[c];
    }
    return last->endw;
}

int PrintPref(Trie* root, char* cuv) {
    if(root == NULL)
        return 0;
    int lenght = strlen(cuv) - 1, lgt = 0, maxfreq;
    Trie* last;
    char c;
    for(int i = 0; cuv[i] != '\0'; ++i) {
        c = cuv[i] - 'a';
        if(!root->poz[c])
            return maxfreq;
        ++maxfreq;
        last = root = root->next[c];
    }
    return maxfreq;
}

int main() {
    f = fopen("trie.in", "r");
    g = fopen("trie.out", "w");
    char cuv[30];
    int operatie, k;
    Trie* root = NULL;
    while(fscanf(f,"%d %s", &operatie, &cuv) == 2) {
        switch(operatie) {
            case 0:
                AddTrie(&root, cuv);
                break;
            case 1:
                DeleteTrie(&root, cuv);
                break;
            case 2:
                k = PrintFreg(root, cuv);
                fprintf(g, "%d\n", k);
                break;
            case 3:
                k = PrintPref(root, cuv);
                fprintf(g, "%d\n", k);
                break;
        }
    }
    return 0;
}