#include <bits/stdc++.h>
using namespace std;
ifstream fi("trie.in");
ofstream fo("trie.out");

struct trie
{
    trie *fiu[26];
    int nrfii, val;

    trie()
    {
        val = nrfii = 0;
        memset(fiu, 0, sizeof(fiu));
    }
};

trie *T = new trie;
int lung;
int rez;
string cuv;

void baga(trie *nod, int poz)
{
    if (poz == lung) /// am terminat cuvantul
    {
        nod->val++;
        return;
    }

    char c = cuv[poz] - 'a';
    if (nod->fiu[c] == 0) /// nu are fiul asta
    {
        nod->fiu[c] = new trie;
        nod->nrfii++;
    }

    baga(nod->fiu[c], poz + 1);
}

int scoate(trie *nod, int poz)
{
    char c = cuv[poz] - 'a';

    if (poz == lung) /// am terminat cuvantul
    {
        nod->val--;
    }
    else if (scoate(nod->fiu[c], poz + 1)) /// a murit fiul
    {
        nod->nrfii--;
        nod->fiu[c] = 0;
    }

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

int ap(trie *nod, int poz)
{
    char c = cuv[poz] - 'a';

    if (poz == lung)
    {
        return nod->val;
    }

    if (nod->fiu[c] == 0)
        return 0;

    return ap(nod->fiu[c], poz + 1);
}

int pre(trie *nod, int poz)
{
    char c = cuv[poz] - 'a';

    if (poz == lung || nod->fiu[c] == 0)
        return poz;

    return pre(nod->fiu[c], poz + 1);
}

int main()
{
    while (!fi.eof())
    {
        int op;
        fi >> op;

        fi >> cuv;

        if (fi.eof())
            break;

        lung = cuv.size();

        if (op == 0)
        {
            baga(T, 0);
        }
        else if (op == 1)
        {
            scoate(T, 0);
        }
        else if (op == 2)
        {
            fo << ap(T, 0) << "\n";
        }
        else if (op == 3)
        {
            fo << pre(T, 0) << "\n";
        }
    }

    return 0;
}