#include <iostream>
#include <string>
#include <sstream>

using namespace std;


struct Element{
	int key;
	int value;
};

struct ElementLL{
	Element elem;
	ElementLL *next, *prev;
};

// Two-way ordered cycled list with sentinel
struct List2W{
	ElementLL *sentinel;
};

void init(List2W& l){
	l.sentinel = new ElementLL();
	l.sentinel->next = l.sentinel;
	l.sentinel->prev = l.sentinel;
}

void insertElem(List2W & l, Element elem){
	ElementLL *element = l.sentinel;
	do {
		if (element->next == l.sentinel || elem.key < element->next->elem.key)
		{
			ElementLL *newelem = new ElementLL;
			newelem->elem = elem;
			newelem->prev = element->next->prev;
			newelem->next = element->next;
			element->next->prev = newelem;
			element->next = newelem;
			break;
		}
		element = element->next;
	} while (element != l.sentinel);
}

bool findKey(List2W & l, int key, Element &elem){
	ElementLL *element = l.sentinel->next;
	while (element != l.sentinel)
	{
		if (element->elem.key == key)
		{
			elem = element->elem;
			return true;
		}
		element = element->next;
	}
	return false;
}

void removeAllKeys(List2W& l, int key){
	if (l.sentinel != l.sentinel->next)
	{
		ElementLL *element = l.sentinel->next;
		while (element != l.sentinel)
		{
			if (element->elem.key == key)
			{
				element->prev->next = element->next;
				element->next->prev = element->prev;
				element = element->next;
			}
			else element = element->next;
		}
	}
}

void showListFromHead(List2W& l){
	ElementLL *elem = l.sentinel->next;
	while (elem != l.sentinel)
	{
		cout << elem->elem.key << "(" << elem->elem.value << "),";
		elem = elem->next;
	}
	cout << endl;
}

void showListFromTail(List2W& l){
	ElementLL *elem = l.sentinel->prev;
	while (elem != l.sentinel)
	{
		cout << elem->elem.key << "(" << elem->elem.value << "),";
		elem = elem->prev;
	}
	cout << endl;
}

void clearList(List2W& l){
	ElementLL *elem = l.sentinel->next;
	while (elem != l.sentinel)
	{
		ElementLL *tmp = elem;
		elem = elem->next;
		delete tmp;
	}
	l.sentinel->next = l.sentinel;
	l.sentinel->prev = l.sentinel;
}

void addList(List2W& l1, List2W& l2){
	if (&l1 != &l2)
	{
		ElementLL *element = l2.sentinel->next;
		while (element != l2.sentinel)
		{
			insertElem(l1, element->elem);
			element = element->next;
		}
		l2.sentinel->next = l2.sentinel;
		l2.sentinel->prev = l2.sentinel;
	}
}

void showBool(bool val){
	if (val)
		cout << "true" << endl;
	else
		cout << "false" << endl;
}

bool isCommand(const string command, const char *mnemonic){
	return command == mnemonic;
}

int main(){
	string line;
	string command;
	List2W *list = NULL;
	int currentL = 0;
	int value;
	cout << "START" << endl;
	while (true){
		getline(cin, line);
		std::stringstream stream(line);
		stream >> command;
		if (line == "" || command[0] == '#')
		{
			// ignore empty line and comment
			continue;
		}

		// copy line on output with exclamation mark
		cout << "!" << line << endl;;

		// change to uppercase
		command[0] = toupper(command[0]);
		command[1] = toupper(command[1]);

		// zero-argument command
		if (isCommand(command, "HA")){
			cout << "END OF EXECUTION" << endl;
			break;
		}

		if (isCommand(command, "SH")) //*
		{
			showListFromHead(list[currentL]);
			continue;
		}

		if (isCommand(command, "ST")) //*
		{
			showListFromTail(list[currentL]);
			continue;
		}

		if (isCommand(command, "CL")) //*
		{
			clearList(list[currentL]);
			continue;
		}

		if (isCommand(command, "IN")) //*
		{
			init(list[currentL]);
			continue;
		}

		// read next argument, one int value
		stream >> value;

		if (isCommand(command, "FK"))
		{
			Element elem;
			bool ret = findKey(list[currentL], value, elem);
			if (ret)
				cout << elem.key << '(' << elem.value << ')' << endl;
			else
				cout << "false" << endl;
			continue;
		}

		if (isCommand(command, "RK"))
		{
			removeAllKeys(list[currentL], value);
			continue;
		}

		if (isCommand(command, "CH"))
		{
			currentL = value;
			continue;
		}

		if (isCommand(command, "IE"))
		{
			int variable2;
			stream >> variable2;
			Element elem;
			elem.key = value;
			elem.value = variable2;
			insertElem(list[currentL], elem);
			continue;
		}

		if (isCommand(command, "GO"))
		{
			list = new List2W[value];
			continue;
		}

		if (isCommand(command, "AD"))
		{
			addList(list[currentL], list[value]);
			continue;
		}
		cout << "wrong argument in test: " << command << endl;
	}
	return 0;
}