#include <iostream>
#include <string>
#include <vector>

std::string str = "none";
const int N = 100000;
const std::string aaa = "aaaaaaaaaaaaaaaaaaaaa";
std::string prev1 = aaa;

struct hashset {
    std::vector<std::string> a[N];
    int get_hash(std::string x) {
        int t = 0;
        for (int i = 0; i < x.length(); i++)
            t += ((i + 1)*int(x[i]));
        return t;
    }
    void add_next(std::string next2, std::string x) {
        int hash = get_hash(x);
        std::string y, prev2;
        for (long long i = 0; i < a[hash].size(); i += 4) {
            if (x == a[hash][i]) {
                y = a[hash][i + 1];
                prev2 = a[hash][i + 2];
                std::swap(a[hash][i], a[hash][a[hash].size() - 4]);
                std::swap(a[hash][i + 1], a[hash][a[hash].size() - 3]);
                std::swap(a[hash][i + 2], a[hash][a[hash].size() - 2]);
                std::swap(a[hash][i + 3], a[hash][a[hash].size() - 1]);
                a[hash].pop_back();
                a[hash].pop_back();
                a[hash].pop_back();
                a[hash].pop_back();
            }
        }
        a[hash].push_back(x);
        a[hash].push_back(y);
        a[hash].push_back(prev2);
        a[hash].push_back(next2);
    }
    void add_prev(std::string prev2, std::string x) {
        int hash = get_hash(x);
        std::string y, next2;
        for (long long i = 0; i < a[hash].size(); i += 4) {
            if (x == a[hash][i]) {
                y = a[hash][i + 1];
                next2 = a[hash][i + 3];
                std::swap(a[hash][i], a[hash][a[hash].size() - 4]);
                std::swap(a[hash][i + 1], a[hash][a[hash].size() - 3]);
                std::swap(a[hash][i + 2], a[hash][a[hash].size() - 2]);
                std::swap(a[hash][i + 3], a[hash][a[hash].size() - 1]);
                a[hash].pop_back();
                a[hash].pop_back();
                a[hash].pop_back();
                a[hash].pop_back();
            }
        }
        a[hash].push_back(x);
        a[hash].push_back(y);
        a[hash].push_back(prev2);
        a[hash].push_back(next2);
    }
    void put(std::string x, std::string y) {
        int hash = get_hash(x);
        std::string tmp1 = prev1;
        std::string tmp2 = aaa;
        int tmp3 = 0;
        for (long long i = 0; i < a[hash].size(); i+=4) {
            if (x == a[hash][i]) {
                tmp1 = a[hash][i + 2];
                tmp2 = a[hash][i + 3];
                tmp3 = 1;
                std::swap(a[hash][i], a[hash][a[hash].size() - 4]);
                std::swap(a[hash][i + 1], a[hash][a[hash].size() - 3]);
                std::swap(a[hash][i + 2], a[hash][a[hash].size() - 2]);
                std::swap(a[hash][i + 3], a[hash][a[hash].size() - 1]);
                a[hash].pop_back();
                a[hash].pop_back();
                a[hash].pop_back();
                a[hash].pop_back();
            }
        }
        a[hash].push_back(x);
        a[hash].push_back(y);
        a[hash].push_back(tmp1);
        a[hash].push_back(tmp2);
        if (tmp3 != 1) {
            if (x != prev1 && prev1 != aaa) add_next(x, prev1);
            prev1 = x;
        }
    }
    void del(std::string x) {
        int hash = get_hash(x);
        for (long long i = 0; i < a[hash].size(); i+=4) {
            if (x == a[hash][i]) {
                if (a[hash][i + 3] == a[hash][i + 2] && a[hash][i + 3] == aaa) prev1 = a[hash][i + 2];
                add_next(a[hash][i + 3], a[hash][i + 2]);
                if (a[hash][i + 3] != aaa) add_prev(a[hash][i + 2], a[hash][i + 3]);
                prev1 = a[hash][i + 2];
                std::swap(a[hash][i], a[hash][a[hash].size() - 4]);
                std::swap(a[hash][i + 1], a[hash][a[hash].size() - 3]);
                std::swap(a[hash][i + 2], a[hash][a[hash].size() - 2]);
                std::swap(a[hash][i + 3], a[hash][a[hash].size() - 1]);
                a[hash].pop_back();
                a[hash].pop_back();
                a[hash].pop_back();
                a[hash].pop_back();
                return;
            }
        }
    }
    std::string get(std::string x) {
        int hash = get_hash(x);
        for (long long i = 0; i < a[hash].size(); i+=4) {
            if (x == a[hash][i] && a[hash][i + 1] != "") return a[hash][i + 1];
        }
        return str;
    }
    std::string next(std::string x) {
        int hash = get_hash(x);
        for (long long i = 0; i < a[hash].size(); i+=4) {
            if (x == a[hash][i] && a[hash][i + 3] != aaa) return get(a[hash][i + 3]);
        }
        return str;
    }
    std::string prev(std::string x) {
        int hash = get_hash(x);
        for (long long i = 0; i < a[hash].size(); i+=4) {
            if (x == a[hash][i] && a[hash][i + 2] != aaa) return get(a[hash][i + 2]);
        }
        return str;
    }
};


int main() {
    std::ios_base::sync_with_stdio(false);
    freopen("linkedmap.in", "r", stdin);
    freopen("linkedmap.out", "w", stdout);
    hashset map = *new hashset();
    std::string text;
    std::string x, y;
    while (std::cin >> text)
    {
        if (text == "put") {
            std::cin >> x >> y;
            map.put(x, y);
        } else if (text == "get") {
            std::cin >> x;
            std::cout << map.get(x) << "\n";
        } else if (text == "next") {
            std::cin >> x;
            std::cout << map.next(x) << "\n";
        } else if (text == "prev") {
            std::cin >> x;
            std::cout << map.prev(x) << "\n";
        } else {
            std::cin >> x;
            map.del(x);
        }
    }
}