#include <bits/stdc++.h>
using namespace std;

ifstream fin("trie.in");
ofstream fout("trie.out");

#define CH (*s - 'a')

struct Trie
{
    int cnt, nrfii;
    Trie *fiu[ 26 ];
    Trie()
    {
        cnt = nrfii = 0;
        memset( fiu, 0, sizeof( fiu ) );
    }
};



Trie *T = new Trie;



void ins( Trie *nod, char *s )
{
    if( *s == '\n' )
    {
        nod->cnt ++;
        return;
    }

    if( nod->fiu[ CH ] == 0 )
    {
        nod->fiu[ CH ] = new Trie;
        nod->nrfii ++;
    }

    ins( nod->fiu[ CH ], s+1 );

}



int del( Trie *nod, char *s )
{

    if( *s == '\n' )
        nod->cnt --;

    else if( del( nod->fiu[ CH ], s+1 ) )
    {
        nod->fiu[ CH ] = 0;
        nod->nrfii --;

    }

    if( nod->cnt == 0 && nod->nrfii == 0 && nod != T )
    {
        delete nod;
        return 1;
    }

    return 0;

}



int que( Trie *nod, char *s )
{
    if(*s == '\n')
        return nod->cnt;

    if( nod->fiu[ CH ] )
        return que( nod->fiu[ CH ], s+1 );

    return 0;
}



int pre( Trie *nod, char *s, int k )
{
    if( *s == '\n' || nod->fiu[ CH ] == 0 )
        return k;
    return pre( nod->fiu[ CH ], s+1, k+1 );
}



int main()
{
  char s[27];
  int x;

  while(fin>>x>>s)
  {
    cout<<x<<' '<<s;
    if(x==0)
      ins(T, s);
    if(x==1)
      del(T, s);
    if(x==2)
      cout<<que(T, s)<< '\n';
    if(x==3)
      cout<<pre(T, s, 0)<< '\n';
  }

}