#include <bits/stdc++.h>

using namespace std;

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

struct nod {
    int x,nrfii,ind,nr;
    nod *fii[26];

    nod() {
        nr=0;
        x=0;
        ind=0;
        nrfii=0;
        memset(fii,0,sizeof(fii));
    }
}*T;

void adaug(char *s,nod *&p) {
    if (p->fii[*s-'a']==0) {
        p->fii[*s-'a']=new nod;
        p->fii[*s-'a']->ind=p->ind+1;
        p->nr++;
    }
    p->fii[*s-'a']->nrfii++;
    p->x-=p->fii[*s-'a']->nrfii;
    if (*(s+1)) adaug(s+1,p->fii[*s-'a']);
    p->x+=p->fii[*s-'a']->nrfii;
    //cout<<*s<<' '<<p->fii[*s-'a']->nrfii<<' '<<p->fii[*s-'a']->ind<<"     ";
}

void q3(char *s,nod *p,int &r) {
    //cout<<s<<' ';
    if (p->fii[*s-'a']!=0) {
        r=max(r,p->fii[*s-'a']->ind);
        if (*(s+1)) q3(s+1,p->fii[*s-'a'],r);
    }
}

void q1(char *s,nod *p) {
    if (p->fii[*s-'a']!=0) {
        if (*(s+1)) q1(s+1,p->fii[*s-'a']);
        p->fii[*s-'a']->nrfii--;
        if (p->fii[*s-'a']->nrfii==0) {
            p->fii[*s-'a']=0;
            p->nr--;
        }
    }
}

void q2(char *s,nod *p,int &r) {
    if (p->fii[*s-'a']!=0) {
        if (*(s+1)) q2(s+1,p->fii[*s-'a'],r);
        else if (p->fii[*s-'a']->nr==0) r=p->fii[*s-'a']->nrfii;
    }
}

int main() {
    char s[26];
    int x,y;
    T=new nod;
    while (f>>x>>s) {
        if (x==0) adaug(s,T);
        else if (x==1) {
            q1(s,T);
        }
        else if (x==2) {
            y=0;
            q2(s,T,y);
            g<<y<<'\n';
        }
        else if (x==3) {
            y=0;
            q3(s,T,y);
            g<<y<<'\n';
        }
        //cout<<'\n';
    }
    return 0;
}