LinkedMap

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <stack>
#include <queue>
#include <deque>
using namespace std;

#define TASK "linkedmap"

vector < pair < string, string > > hash_map[1010101];
vector < pair < int, int > > pr[1010101], nx[1010101];
pair < int, int > prvs = make_pair(-1, -1);

int hash_f(string s) {
    int p = 359;
    int hs = 0;
    for (int i = 0; i < s.size(); i++) {
        hs = (hs * p + s[i]) % 1000000;
    }
    return hs;
}

string get(string key) {
    int hs = hash_f(key);
    for (int i = 0; i < hash_map[hs].size(); i++) {
        if (hash_map[hs][i].first == key) {
            if (hash_map[hs][i].second != "")
                return hash_map[hs][i].second;
        }
    }
    return "";
}

void put(string key, string s) {
    int hs = hash_f(key);
    for (int i = 0; i < hash_map[hs].size(); i++) {
        if (hash_map[hs][i].first == key) {
            hash_map[hs][i].second = s;
            if (prvs != make_pair(-1, -1) && nx[prvs.first][prvs.second] == make_pair(-1, -1)) {
                nx[prvs.first][prvs.second] = make_pair(hs, i);
            }
            return;
        }
    }
    hash_map[hs].push_back(make_pair(key, s));
    pr[hs].push_back(prvs);
    nx[hs].push_back(make_pair(-1, -1));
    if (prvs != make_pair(-1, -1)) {
        nx[prvs.first][prvs.second] = make_pair(hs, pr[hs].size() - 1);
    }
    prvs = make_pair(hs, pr[hs].size() - 1);
}

void del(string key) {
    int hs = hash_f(key);
    for (int i = 0; i < hash_map[hs].size(); i++) {
        if (hash_map[hs][i].first == key) {
            if (hash_map[hs][i].second != "") {
                hash_map[hs][i].second = "";
                pr[nx[hs][i].first][nx[hs][i].second] = pr[hs][i];
                nx[pr[hs][i].first][pr[hs][i].second] = nx[hs][i];
            }
            return;
        }
    }
}

pair < int, int > find(string key) {
    int hs = hash_f(key);
    for (int i = 0; i < hash_map[hs].size(); i++) {
        if (hash_map[hs][i].first == key && hash_map[hs][i].second.size()) {
            return make_pair(hs, i);
        }
    }
    return make_pair(-1, -1);
}

int main() {

#ifdef _DEBUG
    freopen("debug.in", "r", stdin);
    freopen("debug.out", "w", stdout);
#else
    freopen(TASK".in", "r", stdin);
    freopen(TASK".out", "w", stdout);
#endif // _DEBUG

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    string a, key, s;
    while (cin >> a) {
        cin >> key;
        if (a == "put") {
            cin >> s;
            put(key, s);
            continue;
        }
        if (a == "get") {
            s = get(key);
            cout << (s.size() ? s : "none") << "\n";
            continue;
        }
        if (a == "delete") {
            del(key);
            continue;
        }
        pair < int, int > f = find(key);
        if (f == make_pair(-1, -1)) {
            cout << "none\n";
            continue;
        }
        if (a == "next") {
            if (nx[f.first][f.second] == make_pair(-1, -1)) {
                cout << "none\n";
            }
            else {
                cout << hash_map[nx[f.first][f.second].first][nx[f.first][f.second].second].second << "\n";
            }
            continue;
        }
        if (pr[f.first][f.second] == make_pair(-1, -1)) {
            cout << "none\n";
        }
        else {
            cout << hash_map[pr[f.first][f.second].first][pr[f.first][f.second].second].second << "\n";
        }
    }

    return 0;
}