#include <fstream>
#include <list>
#include <string>

using namespace std;

struct item
{
    string key, value;
    item *prev, *next, *after, *before;
};

const int hash_size = 1e6 + 3;

class HashTable {
public:
    item *hashMap[hash_size];
    item *last = nullptr;

    int getHash(string &x) {
        int ans = 0;
        for (int i = 0; i < x.length(); i++) {
            ans *= 31;
            ans %= hash_size;
            ans += x[i] - 'A' + 1;
            ans %= hash_size;
        }
        return ans;
    }

    void Put(string &key, string &value) {
        int h = getHash(key);
        bool changed = false;
        auto it = hashMap[h];
        while (it) {
            if (it->key == key) {
                it->value = value;
                changed = true;
                break;
            }
            it = it->next;
        }
        if (!changed) {
            it = new item();
            it->key = key;
            it->value = value;
            it->prev = nullptr;
            it->next = hashMap[h];

            if (hashMap[h])
                hashMap[h]->prev = it;

            it->after = nullptr;

            if (last)
                last->after = it;

            it->before = last;
            last = it;
            hashMap[h] = it;
        }
    }

    void Delete(string &key) {
        int h = getHash(key);
        auto it = hashMap[h];
        while (it) {
            if (it->key == key) {
                if (!(it->prev)) {
                    if (!(it->next)) {
                        hashMap[h] = nullptr;
                    } else {
                        hashMap[h] = it->next;
                        hashMap[h]->prev = nullptr;
                    }
                } else {
                    if (!(it->next)) {
                        it->prev->next = nullptr;
                    } else {
                        it->prev->next = it->next;
                        it->next->prev = it->prev;
                    }
                }
                if (!(it->after)) {
                    if (!(it->before)) {
                        last = nullptr;
                    } else {
                        last = it->before;
                        it->before->after = nullptr;
                    }
                } else {
                    if (!(it->before)) {
                        it->after->before = nullptr;
                    } else {
                        it->after->before = it->before;
                        it->before->after = it->after;
                    }
                }
                delete it;
                break;
            }
            it = it->next;
        }
    }

    string Get(string &key) {
        string ans = "none";
        int h = getHash(key);
        auto it = hashMap[h];
        while (it) {
            if (it->key == key) {
                ans = it->value;
                break;
            }
            it = it->next;
        }
        return ans;
    }

    string Prev(string &key) {
        string ans = "none";
        int h = getHash(key);
        auto it = hashMap[h];
        while (it) {
            if (it->key == key && it->before) {
                ans = it->before->value;
                break;
            }
            it = it->next;
        }
        return ans;
    }

    string Next(string &key) {
        string ans = "none";
        int h = getHash(key);
        auto it = hashMap[h];
        while (it) {
            if (it->key == key && it->after) {
                ans = it->after->value;
                break;
            }
            it = it->next;
        }
        return ans;
    }
};

int main()
{
    ifstream fin ("linkedmap.in");
    ofstream fout ("linkedmap.out");
    string query;
    HashTable HTable;

    while (fin >> query)
    {
        string x, y;
        fin >> x;
        switch (query[0])
        {
            case 'p':
            {
                if (query[1] == 'u')
                {
                    fin >> y;
                    HTable.Put(x, y);
                }
                else
                {
                    fout << HTable.Prev(x) << '\n';
                }
                break;
            }
            case 'd':
            {
                HTable.Delete(x);
                break;
            }
            case 'g':
            {
                fout << HTable.Get(x) << '\n';
                break;
            }
            case 'n':
            {
                fout << HTable.Next(x) << '\n';
                break;
            }
        }
    }
    return 0;