#include <bits/stdc++.h>
#define int long long
#define TASKNAME "linkedmap"
using namespace std;

const int MOD = 1000033;

struct StringIntHashMap{
    vector<pair<string, int> > arr[MOD];

    StringIntHashMap() {
        for(int i = 0; i < MOD; i ++)
            arr[i] = {};
    }

    int getHash(string x) {
        int cp = 1;
        int res = 0;
        for(auto i : x) {
            res += ((i - 'a' + 1) * cp) % MOD;
            cp *= 53;
            cp %= MOD;
            res %= MOD;
        }
        res = abs(res);
        return res % MOD;
    }

    void put(string x, int y) {
        int hash = getHash(x);
        for(int i = 0; i < arr[hash].size(); i ++)
            if(arr[hash][i].first == x)
            {
                arr[hash][i].second = y;
                return;
            }
        arr[hash].push_back({x, y});
    }

    int get(string x) {
        int hash = getHash(x);
        for(auto i : arr[hash])
            if(i.first == x)
                return i.second;
        return -1;
    }
};

vector<string> keys;
StringIntHashMap* key_pos;

struct HashMap{
    vector<pair<string, string> > arr[MOD];

    HashMap() {
        for(int i = 0; i < MOD; i ++)
            arr[i] = {};
    }

    int getHash(string x) {
        int cp = 1;
        int res = 0;
        for(auto i : x) {
            res += ((i - 'a' + 1) * cp) % MOD;
            cp *= 53;
            cp %= MOD;
            res %= MOD;
        }
        res = abs(res);
        return res % MOD;
    }

    void put(string x, string y) {
        int hash = getHash(x);
        if(key_pos->get(x) == -1)
        {
            key_pos->put(x, keys.size());
            keys.push_back(x);
        }
        for(int i = 0; i < arr[hash].size(); i ++)
            if(arr[hash][i].first == x)
            {
                arr[hash][i].second = y;
                return;
            }
        arr[hash].push_back({x, y});
    }

    bool exists(string x) {
        int hash = getHash(x);
        for(auto i : arr[hash])
            if(i.first == x)
                return 1;
        return 0;
    }

    string get(string x) {
        if(!exists(x))
            return "none";
        int hash = getHash(x);
        for(auto i : arr[hash])
            if(i.first == x)
                return i.second;
        return "none";
    }

    void remove(string x) {
        if(!exists(x))
            return;
        int idx = 0;
        int hash = getHash(x);
        if(arr[hash].size() < 0) return;
        for(int i = 0; i < arr[hash].size(); i ++)
            if(arr[hash][i].first == x)
                idx = i;
        swap(arr[hash][idx], arr[hash][arr[hash].size() - 1]);
        arr[hash].pop_back();
        keys[key_pos -> get(x)] = "";
        key_pos -> put(x, -1);
    }
};

HashMap* hm;

int32_t main() {
    ios_base::sync_with_stdio(0);
    ifstream fin(TASKNAME".in");
    ofstream fout(TASKNAME".out");
    string s;
    string x, y;
    hm = new HashMap();
    key_pos = new StringIntHashMap();
    while(fin >> s) {
        fin >> x;
        if(s == "put")
        {
            fin >> y;
            hm -> put(x, y);
        }
        else if(s == "get")
            fout << (hm -> get(x)) << endl;
        else if(s == "delete")
            hm -> remove(x);
        else if(s == "prev")
        {
            if(!hm -> exists(x))
            {
                fout << "none" << endl;
                continue;
            }
            int pos = key_pos -> get(x);
            if(!pos)
            {
                fout << "none" << endl;
                continue;
            }
            int dec = 1;
            while(pos - dec >= 0 && keys[pos - dec] == "")
                dec++;
            if(pos - dec < 0) {
                fout << "none" << endl;
                continue;
            }
            fout << hm -> get(keys[pos-dec]) << endl;
        } else if(s == "next")
        {
            if(!hm -> exists(x))
            {
                fout << "none" << endl;
                continue;
            }
            int pos = key_pos -> get(x);
            if(pos == keys.size() - 1)
            {
                fout << "none" << endl;
                continue;
            }
            int inc = 1;
            while(pos + inc < keys.size() && keys[pos + inc] == "")
                inc++;
            if(pos + inc >= keys.size()) {
                fout << "none" << endl;
                continue;
            }
            fout << hm -> get(keys[pos+inc]) << endl;
        }
    }
}