#include <bits/stdc++.h>

using namespace std;

class Trie {
    struct Node {
        int cnt = 0;
        int pref = 0;

        Node* pr = nullptr;

        map<char, Node *> next;
    };

    Node* root = nullptr;

    void print(Node* cur, string s);

    string kth(int idx, Node* cur, string s);
public:
    Trie();

    void insert(const string& s);

    void erase(const string& s);

    bool check(const string& s);

    void print();

    string kth(int idx);
};

Trie::Trie() {
    root = new Node();
}

void Trie::insert(const std::string& s) {
    Node* cur = root;

    for (auto i : s) {
        ++cur->pref;
        if (!cur->next[i]) {
            cur->next[i] = new Node();
            cur->next[i]->pr = cur;
        }
        cur = cur->next[i];
    }

    ++cur->cnt;
    ++cur->pref;
}

void Trie::erase(const string& s) {
    Node* cur = root;

    for (auto i : s) {
        if (!cur->next[i]) {
            return;
        }
        cur = cur->next[i];
    }

    if (cur->cnt) {
        --cur->cnt;
        --cur->pref;
        while (cur->pr) {
            cur = cur->pr;
            --cur->pref;
        }
    }
}

bool Trie::check(const string& s) {
    Node* cur = root;

    for (auto i : s) {
        if (!cur->next[i]) {
            return false;
        }
        cur = cur->next[i];
    }

    return cur->cnt;
}

void Trie::print() {
    print(root, "");
}

void Trie::print(Node* cur, string s) {

    for (auto [c, to] : cur->next) {
        if (to) {
            s.push_back(c);
            print(to, s);
            s.pop_back();
        }
    }

    if (cur->cnt) {
        cout << s << '\n';
    }
}

string Trie::kth(int idx) {
    return kth(idx, root, "");
}

string Trie::kth(int idx, Node* cur, string s) {
    if (cur->cnt > idx) {
        return s;
    }
    idx -= cur->cnt;

    for (auto [c, to] : cur->next) {
        if (to->pref > idx) {
            s.push_back(c);
            return kth(idx, to, s);
        }
        idx -= to->pref;
    }

    return "-1";
}

int main() {
    Trie t;

    int q;
    cin >> q;
    while (q--) {
        int tp;
        cin >> tp;

        if (tp == 1) {
            string s;
            cin >> s;
           t.insert(s);
        } else if (tp == 2) {
            string s;
            cin >> s;
            t.erase(s);
        } else if (tp == 3) {
            string s;
            cin >> s;
            cout << t.check(s) << '\n';
            cout << '\n';
        } else if (tp == 4) {
            t.print();
            cout << '\n';
        } else {
            int idx;
            cin >> idx;
            cout << t.kth(idx) << '\n';
            cout << '\n';
        }
    }
}