#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;
}