#include <stdio.h>

#define MAX_LEN 20
#define SIGMA 26
#define MAX_STRINGS 40000

typedef struct {
  char *s;       // șirul de pe muchia incidentă nodului
  int child;     // indicele vectorului de fii (din ptr)
  int parent;    // indicele nodului părinte
  int value;     // numărul de apariții ale șirului
  char numChildren;
} trie;

trie t[MAX_STRINGS * 2];          // deoarece fiecare inserare poate genera două noduri
char str[MAX_STRINGS  * MAX_LEN]; // memorie prealocată pentru șirurile inserate
int ptr[MAX_STRINGS][SIGMA];      // memorie prealocată pentru vectorii de fii
int tsize, psize;                 // numărul de poziții folosite în t și ptr
char *spos;                       // poziția curentă în str

// Salvează o copie a lui s în str și returnează poziția ei
char* saveString(char* s) {
  char *result = spos;
  while (*s) {
    *spos = *s;
    spos++;
    s++;
  }
  *spos = '\0';
  spos++;
  return result;
}

// Navighează prin trie conform șirului s.
// Returnează porțiunea nefolosită din s, nodul u în care a ajuns și
// porțiunea nefolosită din ultima muchie
void navigate(char **s, char **us, int *u) {
  *u = 0;  // pornim din rădăcină
  *us = t[*u].s;
  int ok = 1;

  while (ok) {
    if (**s && **us && (**s == **us)) {
      // s și us continuă cu caractere egale
      (*s)++;
      (*us)++;
    } else if (**s && !**us && t[*u].numChildren && ptr[t[*u].child][**s - 'a']) {
      // Muchia curentă s-a terminat, dar putem continua pe fiul corespunzător
      *u = ptr[t[*u].child][**s - 'a'];
      *us = t[*u].s;
    } else {
      ok = 0;
    }
  }
}

void insert(char *s) {
  int u;
  char *us;
  navigate(&s, &us, &u);
  int parent = t[u].parent;

  if (*us) {
    // Suntem la jumătatea unei muchii. Fie s s-a terminat, fie nu continuă
    // cu caracterul potrivit. Inserăm un nod v între parent și u
    int v = tsize++;
    ptr[t[parent].child][t[u].s[0] - 'a'] = v; // parent pointează acum la v
    t[v].parent = parent;
    t[v].child = psize++;
    t[v].numChildren = 1;
    ptr[t[v].child][*us - 'a'] = u; // v are un singur fiu (pe u)
    char *tmp = saveString(us); // salvăm caracterele neconsumate din us
    *us = '\0'; // încheiem caracterele consumate din us
    t[v].s = t[u].s; // muchia lui v constă din ultimele caractere din s
    t[u].s = tmp;
    t[u].parent = v;
    u = v;
  }

  if (*s) {
    // Suntem într-un nod, iar șirul s continuă. Adăugăm un fiu v.
    int v = tsize++;
    if (!t[u].numChildren) {
      t[u].child = psize++;
    }
    t[u].numChildren++;
    ptr[t[u].child][*s - 'a'] = v;
    t[v].parent = u;
    t[v].s = saveString(s);
    u = v;
  }

  t[u].value++;
}

void erase(char *s) {
  int u;
  char *us;
  navigate(&s, &us, &u);
  t[u].value--;

  // Șterge frunzele care au contor 0
  while (u && !t[u].value && !t[u].numChildren) {
    int parent = t[u].parent;
    ptr[t[parent].child][t[u].s[0] - 'a'] = 0;
    t[parent].numChildren--;
    u = parent;
  }
  // Aici am putea și să compactăm două noduri, dacă au un singur fiu fiecare.
}

int count(char *s) {
  int u;
  char *us;
  navigate(&s, &us, &u);
  return (*s || *us) ? 0 : t[u].value;
}

int prefixMatch(char *s) {
  int u;
  char *us, *sc = s;
  navigate(&s, &us, &u);
  return s - sc;
}

int main(void) {
  FILE *fin = fopen("trie.in", "r");
  FILE *fout = fopen("trie.out", "w");
  int op;
  char s[MAX_LEN + 1];

  // inițializare trie
  str[0] = '\0';
  t[0].s = str;
  tsize = 1;
  psize = 0;
  spos = str + 1;

  while (fscanf(fin, "%d %s", &op, s) == 2) {
    switch (op) {
      case 0: insert(s); break;
      case 1: erase(s); break;
      case 2: fprintf(fout, "%d\n", count(s)); break;
      case 3: fprintf(fout, "%d\n", prefixMatch(s)); break;
    }
  }

  fclose(fin);
  fclose(fout);
}