#include <iostream>
#include <fstream>
#include <cstring>

std::ifstream f ("trie.in");
std::ofstream g ("trie.out");

using namespace std;

struct n_trie
{
    int words_no;
    int chld_no;
    // Luam un sir de pointeri catre fii curentului nod
    n_trie* children[25];
    // Constructorul triei initializeaza valaorile
    n_trie() {
        words_no = 0;
        chld_no = 0;
        memset(children, 0, sizeof(children));
    }
};

n_trie* root = new n_trie();

// Functia care adauga un cuvant in trie
// Primeste ca argumente
void add_word(n_trie* node, char* word) {
    // If we have already reached the last letter of the word
    if (*word == NULL) {
        node -> words_no += 1;
        return;
    }

    int charact = *word - 'a';
    // Daca nu exista fiul pentru litera curenta
    if (node -> children[charact] == 0) {
        // Creaza fiul si continua adaugarea; creste numarul de fii cu 1
///        cout << char(charact + 'a') << " 8 ";
        node -> children[charact] = new n_trie();
        node -> chld_no += 1;
        add_word(node -> children[charact], word + 1);
    }
    else {
        // Daca exista mergi in continuare, pana dai de capat
        add_word(node -> children[charact], word + 1);
    }
}

// Vezi daca exista cuvantul dat in arbore
int query_word(n_trie* node, char* word) {
    // Daca s-a terminat cuvantul, se returneaza nr de cuvinte
    if (*word == 0) {
//        g << " ext ";
        return node -> words_no;
    }

    // Ia codul literei curente
    char nxt_chr = *word - 'a';

    // Daca litera curenta nu exista in arbore, nu mai caut;
    if (node -> children[nxt_chr] == NULL) {
//        g << " ext3 ";
        return 0;
    }
    // Daca litera curenta exista
    else {
        // Continua cautarea cu urmatorul nod si urmatoarea litera
        query_word(node -> children[nxt_chr], word + 1);
        //g << " ok " << *word << ' ';
    }
}

bool delete_word(n_trie* node, char* word) {
    // Daca s-a terminat cuvantul
    if (*word == 0) {
//        g << "exit";
        // si avem pe nodul curent un numar mai mare decat 0, scadem numarul
        if (node -> words_no > 0) {
            node -> words_no -= 1;
            // Daca nu mai este niciun cuvant ramas, stergem nodul si returnam 1
            if (node -> words_no == 0 && node != root) {
///                cout << '\n' << *word << " del\n";
                delete node;
//                g << "1 ";
                return 1;
            }
        }
    }

    int chr = *word - 'a';

///    cout << '\n' << *word << " adel\n";
    // Daca exista nodul curent
    // Apelez functia de stergere pentru urmatorul nod
    if (node -> children[chr] != 0) {
        // Daca s-a sters nodul precedent
        if (delete_word(node -> children[chr], word + 1)) {
            // Scadem numarul de fii ai nodului curent
            node -> chld_no -= 1;
            // Stergem din sirul de adrese pe cea a fiului curent
            node -> children[chr] = 0;

///            cout << '\n' << *word << " delw\n";
            // Cautam printre fii nodului curent ca sa vedem daca mai are
            // vreunul
            if (node -> chld_no == 0 && node != root) {
                // Daca nu mai are fii, il stergem din memorie si returnam 1
///                cout << '\n' << char(chr + 'a') << " del\n";
                delete node;
                return 1;
            }
            // Atentie! Trebuie sters si din sirul de pointeri
            // Stergerea din sirul de pointeri va fi operata de nodul parinte
        }

        return 0;
    }
    // Altfel returnez 0, pentru ca nu s-a sters niciun nod si nici nu
    // s-a ajuns la capatul cuvantului (adica nu exista cuvantul dat
    else {
        return 0;
    }
}

int common_prefix(n_trie* node, char* word) {
    // Daca s-a terminat cuvantul, se returneaza 0
    if (*word == 0) {
        return 0;
    }

    // Ia codul literei curente
    int nxt_chr = *word - 'a';

    // Daca litera curenta nu exista in arbore, nu mai caut si returnez lungimea
    // pana aici
    if (node -> children[nxt_chr] == NULL) {
        return 0;
    }
    // Daca litera curenta exista
    else {
        // Continua cautarea cu urmatorul nod si urmatoarea litera
        return 1 + common_prefix(node -> children[nxt_chr], word + 1);
        //g << " ok " << *word << ' ';
    }
}

int main()
{
    int nr;
    char cuv[22];

    while(!f.eof()) {
        f >> nr;
        f >> cuv;
        // Exit if we have reached the end of file
        if (f.eof())
            break;

        //cout << nr << ' ' << cuv << '\n';
        if (nr == 0){
            add_word(root, cuv);
//            g << '\n';
        }
        else if (nr == 1){
            delete_word(root, cuv);
        }
        // Verifici dac exista prima litera din cuvant in arbore
        else if (nr == 2){
            //g << cuv << ' ';
            g << query_word(root, cuv);
//            g << ' ';
            g << '\n';
        }
        else if (nr == 3){
            g << common_prefix(root, cuv);
            g << '\n';
        }

    }

    //afisare(*root);
    return 0;
}

/// TRASH ///////////////////////////////////////////////////////////////

//void afisare(n_trie nod) {
//    for (int i = 0; i <= 25; ++i) {
//        if (nod.children[i] != 0) {
//            g << char(i + 'a') << ' ';
//        }
//    }
//    g << '\n';
//}