#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("linkedmap.in");
ofstream fout("linkedmap.out");
struct item {
    item* prev = NULL;
    item* prev_key = NULL;
    string key;
    string value;
    item* next_key = NULL;
    item* next = NULL;
};

vector<item*> HashTable = vector<item*>(1000003);

item* CreateNode(string& key, string& value) {
    auto node = new item;
    node->prev = NULL;
    node->prev_key = NULL;
    node->key = key;
    node->value = value;
    node->next_key = NULL;
    node->next = NULL;
    return node;
}

item* AddNode(item*& tail, string& key, string& value) {
    item* node = CreateNode(key, value);
    node->prev = tail;
    tail->next = node;
    return node;
}

long long GetHash(string& key) {
    const int p = 31;
    long long hash = 0, p_pow = 1;
    for (char i : key)
    {
        hash += (i - 'a' + 1) * p_pow;
        p_pow *= p;
    }

    long long m = 1000003;

    if (hash >= 0) {
        return hash % m;
    }
    else {
        return (m - abs(hash) % m) % m;
    }
}

item* Put(string& key, string& value, item*& LastKey) {
    item* head = HashTable[GetHash(key)];
    if (head == NULL) {
        HashTable[GetHash(key)] = CreateNode(key, value);
        HashTable[GetHash(key)]->prev_key = LastKey;

        if (LastKey != NULL)
            LastKey->next_key = HashTable[GetHash(key)];

        return HashTable[GetHash(key)];
    }
    else {
        item* pointer = head;
        while (pointer->next != NULL) {
            if (pointer->key == key) {
                pointer->value = value;
                return NULL;
            }
            pointer = pointer->next;
        }

        if (pointer->key != key) {
            item* new_node = AddNode(pointer, key, value);
            new_node->prev_key = LastKey;
            if (LastKey != NULL)
                LastKey->next_key = new_node;
            return new_node;
        }
        else {
            pointer->value = value;
            return NULL;
        }
    }
}

void Delete(string& key, item*& LastKey) {
    item* pointer = HashTable[GetHash(key)];

    while (pointer != NULL) {
        if (pointer->key == key) {

            if (LastKey == pointer)
                LastKey = pointer->prev_key;

            if (pointer->prev_key != NULL)
                pointer->prev_key->next_key = pointer->next_key;

            if (pointer->next_key != NULL)
                pointer->next_key->prev_key = pointer->prev_key;

            if (pointer->prev != NULL)
                pointer->prev->next = pointer->next;

            if (pointer->next != NULL)
                pointer->next->prev = pointer->prev;

            if (pointer == HashTable[GetHash(key)])
                HashTable[GetHash(key)] = NULL;

            free(pointer);
            return;
        }
        pointer = pointer->next;
    }

}

bool Get(string& key) {
    item* pointer = HashTable[GetHash(key)];

    while (pointer != NULL) {
        if (pointer->key == key) {
            fout << pointer->value << "\n";
            return true;
        }
        pointer = pointer->next;
    }

    fout << "none\n";
    return false;
}

item* Find(string& key) {
    item* pointer = HashTable[GetHash(key)];

    while (pointer != NULL) {
        if (pointer->key == key)
            return pointer;

        pointer = pointer->next;
    }

    return NULL;
}

void Prev(string& key) {
    item* element = Find(key);
    if (element != NULL && element->prev_key != NULL)
        fout << element->prev_key->value << "\n";
    else
        fout << "none\n";
}

void Next(string& key) {
    item* element = Find(key);
    if (element != NULL && element->next_key != NULL)
        fout << element->next_key->value << "\n";
    else
        fout << "none\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);

    item* LastKey = NULL;
    string line;
    string key, value;

    while (fin >> line) {
        fin >> key;
        if (line == "put") {
            fin >> value;
            item* pointer = Put(key, value, LastKey);
            if (pointer != NULL) LastKey = pointer;
        }
        else if (line == "delete") {
            Delete(key, LastKey);
        }
        else if (line == "get") {
            Get(key);
        }
        else if (line == "prev") {
            Prev(key);
        }
        else if (line == "next") {
            Next(key);
        }
    }

    return 0;
}