#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
struct Node
{
    string key;
    string value;

    Node* nextH;
    Node* next;
    Node* prev;

    Node(string key, string value, Node* prev, Node* next)
    {
    	this->key = key;
    	this->value = value;
    	this->nextH = NULL;
    	this->next = next;
		this->prev = prev;
	}

};

struct LinkedHashMap
{
    unsigned int MOD = 96557;
    vector<Node*> table;

    Node* header;


    LinkedHashMap()
    {
        header = new Node("none", "none", NULL, NULL);
        header->prev = header;
        header->next = header;
        table.resize(MOD);
    }

    int hash(string& s)
    {
        int multiplier = 263;
        int prime = 1000000007;
        unsigned long long hash = 0;
        for (int i = s.size() - 1; i >= 0; --i)
            hash = (hash* multiplier + s[i]) % prime;
        return static_cast<int>(hash);
    }


    void add(string& key, string& value)
    {
        Node* x = get_value(key);
        if (x != NULL)
        {
            x->value = value;
            return;
        }
        int h = hash(key);
        Node* elem = new Node(key, value, header->prev, header);
        header->prev->next = elem;
        elem->nextH = table[h % MOD];
        table[h % MOD] = elem;
        header->prev = elem;
    }

    string nextNode(string& key)
    {
        Node* elem = get_value(key);
        return elem == NULL ? "none" : elem->next->value;
    }

    string prev(string& key)
    {
        Node* elem = get_value(key);
        return elem == NULL ? "none" : elem->prev->value;
    }

    string get(string& key)
    {
        Node* elem = get_value(key);
        return elem == NULL ? "none" : elem->value;
    }

    Node* get_value(string& key)
    {
        Node* elem = table[hash(key) % MOD];
        while (elem != NULL)
        {
            if (elem->key == key)
            {
                return elem;
            }
            elem = elem->nextH;
        }
        return NULL;
    }

    void remove(string& key)
    {
        int h = hash(key);
        Node* elem = table[h % MOD];
        Node* prev_elem = NULL;
        while (elem != NULL)
        {
            if (elem->key == key)
            {
                elem->next->prev = elem->prev;
                elem->prev->next = elem->next;
                if (prev_elem == NULL)
                {
                    table[h % MOD] = elem->nextH;
                }
                else
                {
                    prev_elem->nextH = elem->nextH;
                    elem->nextH = NULL;
                }
                return;
            }
            prev_elem = elem;
            elem = elem->nextH;
        }
    }
};


int main()
{
    LinkedHashMap linkedHashMap;
    while (!cin.eof())
    {
        string op;
        string key;
        cin >> op >> key;
        if (op == "put")
        {
            string Node;
            cin >> Node;
            linkedHashMap.add(key, Node);
        }
        if (op == "delete")
        {
            linkedHashMap.remove(key);
        }
        if (op == "get")
        {
            cout << linkedHashMap.get(key) << endl;
        }
        if (op == "prev")
        {
            cout << linkedHashMap.prev(key) << endl;
        }
        if (op == "next")
        {
            cout << linkedHashMap.nextNode(key) << endl;
        }
    }
    return 0;
}