#include<fstream.h>
#include<iostream.h>
#include<cstring>
ifstream f("trie.in");
ofstream g("trie.out");
struct trie
	{ int nrfii,cnt;
      trie *fiu[26];
	  trie()
		  { nrfii=cnt=0;
		    memset (fiu , 0 , sizeof (fiu) );
		  }
	};
trie *T;
char s[32];

void ins(trie *nod, char *p)
{ cout<<*p<<' '<<*p-'a'<<'\n';
  if(*p=='\n') { ++nod->cnt; return;}
  if(nod->fiu[*p-'a'] == 0)
	  { nod->fiu[*p-'a']=new trie;
	    ++ nod->nrfii;
	  }
  ins(nod->fiu[*p-'a'] , p+1);
}

int del(trie *nod, char *p)
{ if(*p=='\n')
	{ -- nod->cnt;
	  if( nod->cnt == 0 && nod->nrfii == 0 && nod!=T ) { delete nod; return 1; }
	  return 0;
	}
  if( del(nod->fiu[*p-'a'],p+1) ) 
	  { nod->fiu[*p-'a']=0;
	    -- nod->nrfii;
		if( nod->cnt == 0 && nod->nrfii == 0 && nod!=T ) { delete nod; return 1; }
	  }
  return 0;
}

int que(trie *nod, char *p)
{ if(*p=='\n') return nod->cnt;
  if(nod->fiu[*p-'a']==0) return 0;
  return que(nod->fiu[*p-'a'],p+1);
}

int pre(trie *nod, char *p)
{ if(*p=='\n' || nod->fiu[*p-'a']==0) return 0;
  return 1+pre(nod->fiu[*p-'a'],p+1);
}

int main()
{ f.getline(s,32);
  while( !f.eof() )
	  { cout<<s<<' '<<s[0]<<' '<<*(s+2)<<'\n';
		switch(s[0])
		  { case '0': ins(T, s+2); break;
			case '1': del(T, s+2); break;
			case '2': g<<que(T,s+2)<<'\n'; break;
			case '3': g<<pre(T,s+2)<<'\n'; break;
		  }
		f.getline(s,32);
	  }
  switch(s[0])
		{ case '0': ins(T, s+2); break;
		  case '1': del(T, s+2); break;
		  case '2': g<<que(T,s+2)<<'\n'; break;
		  case '3': g<<pre(T,s+2)<<'\n'; break;
		}
  f.close(); g.close();
  return 0;
}