#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define Nadejde 100000
#define Smerenie 21
#define NIL -1

int N, size;
int task[Nadejde];            // task[i] este tipul intrebarii "i".
int count[Nadejde];           // count[i] este frecventa pozitiei "i".
char s[Nadejde][Smerenie];    // sirurile din intrebari.
char dict[Nadejde][Smerenie]; // dictionarul sortat.

/** max(X, Y). **/
int MAX(int X, int Y) {
  return X > Y ? X : Y;
}

/** Sorteaza crescator dictionarul. **/
void sort(int begin, int end) {
  int b = begin, e = end;
  char tmp[Smerenie], pivot[Smerenie];
  strcpy(pivot, dict[(b + e) >> 1]);

  while (b <= e) {
    while (strcmp(dict[b], pivot) < 0) {
      b++;
    }
    while (strcmp(dict[e], pivot) > 0) {
      e--;
    }
    if (b <= e) {
      strcpy(tmp, dict[b]);
      strcpy(dict[b++], dict[e]);
      strcpy(dict[e--], tmp);
    }
  }
  if (begin < e) {
    sort(begin, e);
  }
  if (b < end) {
    sort(b, end);
  }
}

/** Sterge dublurile. **/
void unique() {
  int i, count = 1;
  for (i = 1; i < size; i++) {
    if (strcmp(dict[i], dict[count - 1])) {
      strcpy(dict[count++], dict[i]);
    }
  }
  size = count;
}

/** Cauta binar sirul "s" in dictionar. **/
int bSearch(int lo, int hi, char *s) {
  while (hi - lo > 1) {
    int mid = (lo + hi) >> 1;
    if (strcmp(dict[mid], s) > 0) {
      hi = mid;
    } else {
      lo = mid;
    }
  }
  return lo;
}

/** Adauga la "count" valoarea "val". **/
void add(char *s, int val) {
  count[bSearch(NIL, size, s)] += val;
}

/** Gaseste frecventa sirului "s". **/
int get(char *s) {
  int pos = bSearch(NIL, size, s);
  return (pos < 0) || (strcmp(dict[pos], s)) ? 0 : count[pos];
}

/** Lungimea celui mai lung prefix comun. **/
int common(char *u, char *v) {
  int pos = 0;
  while ((u[pos]) && (u[pos] == v[pos])) {
    pos++;
  }
  return pos;
}

/** Raspunde la intrebarile de tip 3. **/
int match(char *s) {
  int pos = bSearch(NIL, size, s);
  /* Daca sirul "s" este mai mic decat celalte siruri. */
  if (pos < 0) {
    do {
      pos++;
    } while (!count[pos]);
    return common(s, dict[pos]);
  } else {
    /* Afla cuvintele cu care "s" face prefixul comun maxim. */
    int lo = pos, hi = pos + 1;
    while ((lo >= 0) && (!count[lo])) {
      lo--;
    }
    while ((hi < size) && (!count[hi])) {
      hi++;
    }
    return MAX(lo >= 0 ? common(s, dict[lo]) : 0, hi < size ? common(s, dict[hi]) : 0);
  }
}

int main(void) {
  int i;
  FILE *f = fopen("trie.in", "r");

  /* Citeste intrebarile si memoreaza-le. */
  while (fscanf(f, "%d %s", &task[N], s[N]) == 2) {
    if (!task[N]) {
      strcpy(dict[size++], s[N]);
    }
    N++;
  }
  fclose(f);

  f = fopen("trie.out", "w");

  sort(0, size - 1);
  unique();

  /* Raspunde la intrebari. */
  for (i = 0; i < N; i++) {
    switch(task[i]) {
      case 0 : add(s[i], -NIL);
        break;
      case 1 : add(s[i], NIL);
        break;
      case 2 : fprintf(f, "%d\n", get(s[i]));
        break;
      case 3 : fprintf(f, "%d\n", match(s[i]));
        break;
    }
  }
  fclose(f);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}