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

typedef struct trie
{
    char value;
    int end;
    struct trie *child;
    struct trie *sibling;
} * Trie;

Trie initTrie(char value, int end)
{
    Trie root = malloc(sizeof(struct trie));
    root->value = value;
    root->end = end;
    root->child = NULL;
    root->sibling = NULL;
    return root;
}

Trie insertChild(Trie trie, char value, int end)
{
    if (trie == NULL)
    {
        return initTrie(value, end);
    }
    if (trie->child == NULL)
    {
        trie->child = initTrie(value, end);
        return trie;
    }
    Trie tmp = trie->child;
    while (tmp->sibling != NULL)
    {
        tmp = tmp->sibling;
    }
    tmp->sibling = initTrie(value, end);
    return trie;
}

Trie getChild(Trie trie, char value)
{
    if (trie == NULL)
    {
        return NULL;
    }
    Trie tmp = trie->child;
    while (tmp != NULL)
    {
        if (tmp->value == value)
        {
            return tmp;
        }
        tmp = tmp->sibling;
    }
    return NULL;
}

Trie insertWord(Trie trie, char *word, int index)
{
    if (index == strlen(word))
    {
        trie->end++;
        return trie;
    }
    Trie child;
    child = getChild(trie, word[index]);
    if (child == NULL)
    {
        trie = insertChild(trie, word[index], 0);
        child = getChild(trie, word[index]);
    }
    child = insertWord(child, word, index + 1);
    return trie;
}

int containsWord(Trie trie, char *word, int index)
{
    if (index == strlen(word) && trie->end >= 1)
    {
        return trie->end;
    }
    Trie p = trie->child;
    while (p)
    {
        if (p->value == word[index])
            return containsWord(p, word, index + 1);
        p = p->sibling;
    }
    return 0;
}

Trie deleteChild(Trie trie, char value)
{
    if (!trie)
        return NULL;
    Trie p = trie->child;
    if (trie->child->value == value)
    {
        Trie todel = trie->child;
        trie->child = trie->child->sibling;
        free(todel);
        return NULL;
    }
    while (p->sibling)
    {
        if (p->sibling->value == value)
        {
            Trie todel = p->sibling;
            p->sibling = p->sibling->sibling;
            free(todel);
            return NULL;
        }
        p = p->sibling;
    }
    return trie;
}

Trie deleteWord(Trie trie, char *word, int index)
{
    Trie p = trie->child;
    while (p)
    {
        if (p->value == word[index])
        {
            if (index == strlen(word) - 1)
                p->end = 0;
            else
                deleteWord(p, word, index + 1);
        }
        if (p->child == NULL && !p->end)
        {
            deleteChild(trie, p->value);
            return trie;
        }
        p = p->sibling;
    }
    return trie;
}

int longest_prefix(Trie trie, char *word, int index)
{
    Trie p = trie->child;
    while (p)
    {
        if (p->value == word[index])
            return longest_prefix(p, word, index + 1);
        p = p->sibling;
    }
    return index;
}

Trie freeTrie(Trie trie)
{
    Trie p = trie->child;
    while (p)
    {
        freeTrie(p);
        Trie todel = p;
        p = p->sibling;
        free(todel);
    }
    return trie;
}

int main()
{
    FILE *in = fopen("trie.in", "r");
    FILE *out = fopen("trie.out", "w");
    Trie trie = NULL;
    trie = initTrie(' ', 0);
    int op;
    char cuv[30];
    while (fscanf(in, "%d %s", &op, cuv) == 2)
    {
        if (op == 0)
            trie = insertWord(trie, cuv, 0);
        else if (op == 1)
            trie = deleteWord(trie, cuv, 0);
        else if (op == 2)
            fprintf(out, "%d\n", containsWord(trie, cuv, 0));
        else
            fprintf(out, "%d\n", longest_prefix(trie, cuv, 0));
    }
    trie = freeTrie(trie);
    fclose(in);
    fclose(out);
    return 0;
}