#include <iostream>
#include <functional>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
#include <list>
#include <unordered_map>
using namespace std;

#define mp make_pair


struct List {
    List() : next(nullptr), prev(nullptr), value("") {
    }
    List *next = nullptr;
    List *prev = nullptr;
    string value;
};
struct Node {
    string first;
    string second;
    List *a;
};
List *last = nullptr;
struct HashTable {
    HashTable() : v(vector<vector<Node>>(size)) {
        p.push_back(37);
        for (int i = 0; i < 100; ++i) {
            p.push_back(p.back() * 37);
        }
    }

    unsigned int hash(string x) {
        unsigned int pos = 0;
        for (size_t i = 0; i < x.size(); ++i) {
            pos += x[i] * p[i];
        }

        return pos % size;
    }
    string get(string x) {
        if (!exists(x)) return "none";
        int pos = hash(x);
        int i = find_pos(v[pos], x);
        return v[pos][i].second;
    }
    bool exists(const string &x) {
        int pos = hash(x);
        for (size_t i = 0; i < v[pos].size(); ++i) {
            if (v[pos][i].first == x) return 1;
        }
        return 0;
    }
    int find_pos(const vector<Node> &mas, const string s) {
        for (size_t i = 0; i < mas.size(); ++i) {
            if (mas[i].first == s) {
                return (int)i;
            }
        }
        return -1;
    }
    void insert(string x, string s) {
        if (exists(x)) {
            int pos = hash(x);
            int i = find_pos(v[pos], x);

            v[pos][i].second = s;
            return;
        }
        List *l = new List();
        l->prev = last;
        l->value = x;
        if (last != nullptr) last->next = l;
        last = l;
        Node q;
        q.first = x;
        q.second = s;
        q.a = l;
        cur_size++;
        v[hash(x)].push_back(q);
    }
    void erase(string &x) {
        if (!exists(x)) {
            return;
        }
        cur_size--;
        int pos = hash(x);
        int i = find_pos(v[pos], x);
        if (v[pos][i].a->prev != nullptr) {
            v[pos][i].a->prev->next = v[pos][i].a->next;
        }
        if (v[pos][i].a->next != nullptr) {
            v[pos][i].a->next->prev = v[pos][i].a->prev;
        } else {
            last = v[pos][i].a->prev;
        }
        delete v[pos][i].a;
        v[pos].erase(v[pos].begin() + i);
    }
    string next(const string x) {
        if (!exists(x)) {
            return "none";
        }
        int pos = hash(x);
        int i = find_pos(v[pos], x);
        if (v[pos][i].a->next == nullptr) {
            return "none";
        }
        return get(v[pos][i].a->next->value);
    }
    string prev(const string x) {
        if (!exists(x)) {
            return "none";
        }
        int pos = hash(x);
        int i = find_pos(v[pos], x);
        if (v[pos][i].a->prev == nullptr) {
            return "none";
        }
        return get(v[pos][i].a->prev->value);
    }
    int cur_size = 0;
    int size = 1000000;
    vector<vector<Node>> v;
    vector<int> p;
};

int main() {
#ifdef _KOCH
    freopen("read.txt", "r", stdin);
#else
    freopen("linkedmap.in", "r", stdin);
    freopen("linkedmap.out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string s;
    HashTable h;
    while (cin >> s) {
        string x;
        cin >> x;
        if (s[0] == 'p' && s[1] == 'u') {
            string f;
            cin >> f;
            h.insert(x, f);
            continue;
        }
        if (s[0] == 'g') {
            cout << h.get(x) << "\n";
            continue;
        }
        if (s[0] == 'd') {
            h.erase(x);
            continue;
        }
        if (s[0] == 'n') {
            cout << h.next(x) << "\n";
            continue;
        }
        if (s[0] == 'p' && s[1] == 'r') {
            cout << h.prev(x) << "\n";
        }
    }
    return 0;
}