/*
 * =====================================================================================
 *
 *       Filename:  trie.cpp
 *
 *    Description: http://www.infoarena.ro/problema/trie 
 *                 http://www.infoarena.ro/job_detail/1449427?action=view-source  
 *
 *        Version:  1.0
 *        Created:  06/09/2015 02:19:02 PM
 *       Revision:  none
 *       Compiler:  gcc/g++
 *
 *         Author:  Marius-Constantin Melemciuc  
 *          email:  
 *   Organization:  
 *
 * =====================================================================================
 */
 
#include <iostream>
#include <vector>
#include <string>
#include <fstream>
 
using namespace std;
 
const int alphabet_size = 26;
string str;
 
struct Trie {
    int count_childs, count_words; 
    vector<Trie*> child;
 
    Trie() {
        count_childs = count_words = 0;
        child.resize(alphabet_size, NULL);
    }
};
 
Trie* root;
 
void pushToTrie(Trie* node, int letter) {
    if (letter == str.size()) {
        node->count_words++;
        return;
    }
    if (node->child[str[letter] - 'a'] == NULL) {
        node->child[str[letter] - 'a'] = new Trie;
        node->count_childs++;
    }
 
    pushToTrie(node->child[str[letter] - 'a'], letter + 1);
}

bool popFromTrie(Trie* node, int letter) {
    if (letter == str.size()) {
        node->count_words--;
    } else {
        if (popFromTrie(node->child[str[letter] - 'a'], letter + 1) == 1) {
            node->count_childs--;
            node->child[str[letter] - 'a'] = NULL;
        }
    }
 
    if (node->count_childs == 0 && 
        node->count_words == 0 && 
        node != root) { // if the node doesn't have any childs and 
                        // doesn't have words that terminate in him and 
                        // is not the trie root
        delete node;
        return 1;
    }
 
    return 0;
}

bool popFromTrie(Trie* node, int letter) {
   if (letter == str.size()) {
    node->count_words--;
   } else {
       
   }
}

int getNumberOfWords(Trie* node, int letter) {
    if (letter == str.size()) 
        return node->count_words;
 
    if (node->child[str[letter] - 'a'] != NULL) 
        return getNumberOfWords(node->child[str[letter] - 'a'], 
                                letter + 1);
 
    return 0;
}
 
int getNumberOfPrefixes(Trie* node, int letter) {
    if (letter == str.size() || node->child[str[letter] - 'a'] == NULL)
        return letter;
 
    return getNumberOfPrefixes(node->child[str[letter] - 'a'], letter + 1);
}
 
int main() {
    int operation; 
    ifstream input("trie.in");
    ofstream output("trie.out");
 
    root = new Trie;
 
    while (input >> operation >> str) {
        if (operation == 0) 
            pushToTrie(root, 0);
        if (operation == 1)
            popFromTrie(root, 0);
        if (operation == 2) 
            output << getNumberOfWords(root, 0) << '\n';
        if (operation == 3)
            output << getNumberOfPrefixes(root, 0) << '\n';
    }
 
    input.close();
    output.close();
 
    return 0;
}