qazwsx

#define _CRT_SECURE_NO_WARNINGS
#define SIZE (int)1e+4 + 7
#include <iostream>
#include <vector>
#include <string>
using namespace std;

struct Node {
    string key;
    string val;
    bool exs;
    Node *prev;
    Node *next;
} *last = NULL;

vector <vector <Node> > hash_t(SIZE);

int hashFunc(string key) {
    int p = 137;
    int p_pow = 1;
    int hash = 0;
    for (size_t i = 0; i < key.size(); i++) {
        hash += (int)key[i] * p_pow;
        p_pow *= p; p_pow = abs(p_pow) % SIZE;
        hash %= SIZE;
    }
    return hash;
}

void makePair(string key, string val);
void deleteKey(string key);
void getVal(string key);
void prevVal(string key);
void nextVal(string key);

int main() {
    ios_base::sync_with_stdio(false);

    freopen("linkedmap.in", "r", stdin);
    freopen("linkedmap.out", "w", stdout);

    string operation, key, value;
    while (cin >> operation) {
        cin >> key;
        if (operation == "put") {
            cin >> value;
            makePair(key, value);
        }
        else if (operation == "delete")
            deleteKey(key);
        else if (operation == "get")
            getVal(key);
        else if (operation == "prev")
            prevVal(key);
        else if (operation == "next")
            nextVal(key);
    }
    return 0;
}

void makePair(string key, string val) {
    int hash = hashFunc(key);
    for (size_t i = 0; i < hash_t[hash].size(); i++) {
        if (hash_t[hash][i].key == key) {
            if (hash_t[hash][i].exs == false) {
                hash_t[hash][i].exs = true;
                hash_t[hash][i].prev = last;
                hash_t[hash][i].next = NULL;
                if (last != NULL) {
                    last->next = &hash_t[hash][i];
                }
                last = &hash_t[hash][i];
            }
            hash_t[hash][i].val = val;
            return;
        }
    }
    Node *temp = new Node;
    hash_t[hash].push_back(*temp);
    hash_t[hash].back().key = key;
    hash_t[hash].back().val = val;
    hash_t[hash].back().exs = true;
    hash_t[hash].back().next = NULL;
    hash_t[hash].back().prev = last;
    if (last != NULL)
        last->next = &hash_t[hash].back();
    last = &hash_t[hash].back();
    delete temp;
}

void deleteKey(string key) {
    int hash = hashFunc(key);
    for (size_t i = 0; i < hash_t[hash].size(); i++) {
        if (hash_t[hash][i].key == key) {
            if (hash_t[hash][i].exs == true) {
                Node *prev = hash_t[hash][i].prev;
                Node *next = hash_t[hash][i].next;
                if (prev != NULL)
                    prev->next = next;
                if (next != NULL)
                    next->prev = prev;
                if (prev == NULL && next == NULL)
                    last = NULL;
                else if (next == NULL)
                    last = prev;
                hash_t[hash][i].exs = false;
                return;
            }
            return;
        }
    }
}

void getVal(string key) {
    int hash = hashFunc(key);
    for (size_t i = 0; i < hash_t[hash].size(); i++)
        if (hash_t[hash][i].key == key && hash_t[hash][i].exs == true) {
            cout << hash_t[hash][i].val << endl;
            return;
        }
    cout << "none" << endl;
}

void prevVal(string key) {
    int hash = hashFunc(key);
    for (size_t i = 0; i < hash_t[hash].size(); i++)
        if (hash_t[hash][i].key == key && hash_t[hash][i].exs == true) {
            if (hash_t[hash][i].prev != NULL)
                cout << hash_t[hash][i].prev->val << endl;
            else
                cout << "none" << endl;
            return;
        }
    cout << "none" << endl;
}

void nextVal(string key) {
    int hash = hashFunc(key);
    for (size_t i = 0; i < hash_t[hash].size(); i++)
        if (hash_t[hash][i].key == key && hash_t[hash][i].exs == true) {
            if (hash_t[hash][i].next != NULL)
                cout << hash_t[hash][i].next->val << endl;
            else
                cout << "none" << endl;
            return;
        }
    cout << "none" << endl;
}