#include<cstdio>
#include<algorithm>
#include<cstring>
#include<algorithm>
using namespace std;
char s[30],operations[100010],words[100010][21];
int dictionary[100010],apparitions[100010],dictionary_size=0;
bool cmp(int a,int b){
    if(strcmp(words[a],words[b])<0)
        return true;
    return false;
}
int common_prefix(int pointer,int position){
    int result=0;
    while(words[pointer][result]==words[dictionary[position]][result]&&words[pointer][result]!=NULL)
        result++;
    return result;
}
int binary_string_search(int pointer){
    int left=1,right=dictionary_size+1,middle,position,maximum_position,maximum_common=0;
    if(strcmp(words[pointer],words[dictionary[1]])<0)
        return 0;
    while(left<=right){
        middle=(left+right)/2;
        position=common_prefix(pointer,middle);
        if(words[pointer][position]==NULL&&words[dictionary[middle]][position]==NULL)
            return middle;
        if(position>maximum_common){
            maximum_common=position;
            maximum_position=middle;
        }
        if(words[pointer][position]>=words[dictionary[middle]][position])
            left=middle+1;
        else
            right=middle-1;
    }
    return maximum_position;
}
void change_count(int pointer,int value){
    int position=binary_string_search(pointer);
    apparitions[position]+=value;
}
int get_count(int pointer){
    int position=binary_string_search(pointer);
    if(strcmp(words[pointer],words[dictionary[position]])!=0)
        return 0;
    return apparitions[position];
}
int maximum(int a,int b){
    if(a<b)
        return b;
    return a;
}
int get_maximum_prefix(int pointer){
    int position=binary_string_search(pointer),position_copy,auxiliar,maximum_prefix=0;
    if(position==0){
        position++;
        while(apparitions[position]==0)
            position++;
        return common_prefix(pointer,position);
    }
    position_copy=position;
    while(position>0&&apparitions[position]==0)
        position--;
    if(position>0)
        maximum_prefix=maximum(maximum_prefix,common_prefix(pointer,position));
    position=position_copy;
    while(position<=dictionary_size&&apparitions[position]==0)
        position++;
    if(position<=dictionary_size)
        maximum_prefix=maximum(maximum_prefix,common_prefix(pointer,position));
    return maximum_prefix;
}
int main(){
    FILE *fin = fopen("trie.in", "r");
    FILE *fout = fopen("trie.out", "w");
    int n=1,i,auxiliar=0;
    while(fscanf(fin,"%d %s",&operations[n],&words[n])==2){
        if(operations[n]==0){
            dictionary_size++;
            dictionary[dictionary_size]=n;
        }
        n++;
    }
    n--;
    sort(dictionary+1,dictionary+dictionary_size+1,cmp);
    for(i=1;i<=dictionary_size;i++)
        if(strcmp(words[dictionary[i]],words[dictionary[i-1]])!=0){
            auxiliar++;
            dictionary[auxiliar]=dictionary[i];
        }
    dictionary_size=auxiliar;
    for(i=1;i<=n;i++){
        if(operations[i]==0)
            change_count(i,1);
        if(operations[i]==1)
            change_count(i,-1);
        if(operations[i]==2)
            fprintf(fout,"%d\n",get_count(i));
        if(operations[i]==3)
            fprintf(fout,"%d\n",get_maximum_prefix(i));
    }
    fclose(fin);
    fclose(fout);
    return 0;
}