#include <fstream>
#include <vector>
using namespace std;


struct ListElement
{
    string key, value;
    ListElement *chain;
    ListElement *next_element, *previous_element;
};

class List
{
    ListElement *newlist;
public:
    List();
    void Insert(const string& Key, const string& Value, ListElement *Head);
    void Delete(const string& Key, ListElement *Head);
    ListElement* Search(const string& Key);
};

List::List()
{
    newlist = new ListElement();
    newlist->value = newlist->key = "";
    newlist->chain = nullptr;
}

void List::Insert(const string& Key, const string& Value, ListElement *Head)
{
    ListElement *NewNode = Search(Key);
    if (Search(Key) == nullptr)
    {
        NewNode = new ListElement;
        NewNode->key = Key;
        NewNode->value = Value;
        NewNode->chain = newlist->chain;
        newlist->chain = NewNode;
        ListElement *Tail = Head->previous_element;
        Tail->next_element = NewNode;
        Head->previous_element = NewNode;
        NewNode->next_element = Head;
        NewNode->previous_element = Tail;
    }
    else
    {
        NewNode->value = Value;
    }
}

void List::Delete(const string& Key, ListElement *Head)
{
    ListElement *CurNode = newlist;
    while (CurNode->chain != nullptr)
    {
        if (CurNode->chain->key == Key)
        {
            ListElement *NodeToDel = CurNode->chain;
            CurNode->chain = CurNode->chain->chain;
            ListElement *PrevNode = NodeToDel->previous_element, *NextNode = NodeToDel->next_element;
            NodeToDel->previous_element->next_element = NextNode;
            NodeToDel->next_element->previous_element = PrevNode;
            delete NodeToDel;
            return;
        }
        else
        {
            CurNode = CurNode->chain;
        }
    }
}

ListElement* List::Search(const string& Key)
{
    ListElement *current = newlist;
    while (current->chain != nullptr)
    {
        if (current->chain->key == Key)
        {
            return current->chain;
        }
        else
        {
            current = current->chain;
        }
    }
    return nullptr;
}

class LinkedMap
{
    vector<List> source;
    ListElement *Head;
    int StringToHash(string Key);
public:
    LinkedMap();
    void Insert(const string& Key, const string& Value);
    void Delete(const string& Key);
    string Search(const string& Key);
    string Next(const string& Key);
    string Prev(const string& Key);
};

LinkedMap::LinkedMap()
{
    source.resize(1000);
    Head = new ListElement;
    Head->previous_element = Head->next_element = Head;
}

int LinkedMap::StringToHash(string Key)
{
    unsigned int res = 0, pow = 1, p = 31, s = source.size();
    for (int i = 0; i < Key.length(); ++i)
    {
        res += (Key[i] - 'A') * pow;
        pow *= p;
    }
    return res % s;
}

void LinkedMap::Insert(const string& Key, const string& Value)
{
    source[StringToHash(Key)].Insert(Key, Value, Head);
}

string LinkedMap::Search(const string& Key)
{
    ListElement *Res = source[StringToHash(Key)].Search(Key);
    if (Res == nullptr)
        return "none";
    else
        return Res->value;
}

void LinkedMap::Delete(const string& Key)
{
    source[StringToHash(Key)].Delete(Key, Head);
}

string LinkedMap::Next(const string& Key)
{
    ListElement *Res = source[StringToHash(Key)].Search(Key);
    if (Res == nullptr || Res->next_element == Head)
        return "none";
    else
        return Res->next_element->value;
}

string LinkedMap::Prev(const string& Key)
{
    ListElement *Res = source[StringToHash(Key)].Search(Key);
    if (Res == nullptr || Res->previous_element == Head)
        return "none";
    else
        return Res->previous_element->value;
}

int main()
{
    ifstream fin("linkedmap.in");
    ofstream fout("linkedmap.out");
    LinkedMap LM;
    string command;
    while (fin >> command)
    {
        string K, V;
        if (command == "put")
        {
            fin >> K >> V;
            LM.Insert(K, V);
        }
        else if (command == "delete")
        {
            fin >> K;
            LM.Delete(K);
        }
        else if (command == "get")
        {
            fin >> K;
            fout << LM.Search(K) << "\n";
        }
        else if (command == "next")
        {
            fin >> K;
            fout << LM.Next(K) << "\n";
        }
        else if (command == "prev")
        {
            fin >> K;
            fout << LM.Prev(K) << "\n";
        }
    }
    return 0;
}