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

#define MAX_N 100000
#define MAX_LEN 20
int op[MAX_N];
char s[MAX_N][MAX_LEN + 1];
char *dict[MAX_N];
int dsize;
int count[MAX_N];  // numărul de apariții ale cuvântului corespunzător din dict[].

void tsort(char **s, int lo, int hi, int pos) {
  if (lo >= hi) {
    return;
  }

  int curr = lo, left = lo, right = hi;
  char mid = (s[lo][pos] + s[hi][pos]) / 2;
  char *tmp;

  while (curr <= right) {
    char c = s[curr][pos];
    if (c < mid) {
      tmp = s[curr];
      s[curr] = s[left];
      s[left] = tmp;
      left++;
      curr++;
    } else if (c > mid)  {
      tmp = s[curr];
      s[curr] = s[right];
      s[right] = tmp;
      right--;
    }  else {
      curr++;
    }
  }

  tsort(s, lo, left - 1, pos);
  if (s[left][pos] != '\0' ) {
    tsort(s, left, right, pos + 1);
  }
  tsort(s, right + 1, hi, pos);
}

// Returnează poziția celui mai mare șir din dict[] care este mai mic sau egal cu s.
// Returnează -1 dacă toate șirurile din dict[] sunt mai mari ca s.
int binSearch(char *s) {
  if (strcmp(s, dict[0]) < 0) {
    return -1;
  }
  int lo = 0, hi = dsize, mid;
  while (hi - lo > 1) {
    mid = (lo + hi) / 2;
    if (strcmp(s, dict[mid]) >= 0) {
      lo = mid;
    } else {
      hi = mid;
    }
  }
  return lo;
}

void change(char *s, int val) {
  int pos = binSearch(s);
  count[pos] += val;
}

int get(char *s) {
  int pos = binSearch(s);
  return ((pos == -1) || strcmp(s, dict[pos])) ? 0 : count[pos];
}

int commonPrefix(char *a, char *b) {
  int r = 0;
  while (a[r] && (a[r] == b[r])) {
    r++;
  }
  return r;
}

int prefixMatch(char *s) {
  int pos = binSearch(s);
  if (pos == -1) {
    do {
      pos++;
    } while (!count[pos]);
    return commonPrefix(s, dict[pos]);
  }

  int result = 0;
  int posCopy = pos;
  while (pos >= 0 && !count[pos]) {
    pos--;
  }
  if (pos >= 0) {
    result = commonPrefix(s, dict[pos]);
  }
  pos = posCopy + 1;
  while (pos < dsize && !count[pos]) {
    pos++;
  }
  if (pos < dsize) {
    int candidate = commonPrefix(s, dict[pos]);
    if (candidate > result) {
      result = candidate;
    }
  }
  return result;
}

int main(void) {
  FILE *fin = fopen("trie.in", "r");
  FILE *fout = fopen("trie.out", "w");
  int numOps = 0;

  // colectează toate șirurile care vor exista vreodată în structură
  while (fscanf(fin, "%d %s", &op[numOps], s[numOps]) == 2) {
    if (op[numOps] == 0) {
      dict[dsize++] = s[numOps];
    }
    numOps++;
  }

  // sortează șirurile și elimină duplicatele
  tsort(dict, 0, dsize - 1, 0);
  int pos = 1; // numărul de șiruri păstrate până acum
  for (int i = 1; i < dsize; i++) {
    if (strcmp(dict[i], dict[pos - 1])) {
      dict[pos++] = dict[i];
    }
  }
  dsize = pos;

  // procesează comenzile
  for (int i = 0; i < numOps; i++) {
    switch (op[i]) {
      case 0: change(s[i], 1); break;
      case 1: change(s[i], -1); break;
      case 2: fprintf(fout, "%d\n", get(s[i])); break;
      case 3: fprintf(fout, "%d\n", prefixMatch(s[i])); break;
    }
  }  


  fclose(fin);
  fclose(fout);
}