#include "stdafx.h"
#include <iostream>
#include <cstring>

using namespace std;

class Node {
public:

	char bukwa;
	char* pos;
	class Node *prev, *next;

	void swap(Node* n) {
		char tempb = this->bukwa;
		char* tempp = this->pos;
		this->bukwa = n->bukwa;
		this->pos = n->pos;
		n->pos = tempp;
		n->bukwa = tempb;
	}


	//    Node(Node* n){
	//        this->bukwa = n->bukwa;
	//        this->pos = n->pos;
	//        this->next = n->next;
	//        this->prev = n->prev;
	//    }

	Node(char bukwa, char* napis) {
		this->bukwa = bukwa;
		pos = new char[65];
		int i = 0;
		if (!*napis)
			*pos = '\0';
		else {
			while (*(napis + i)) {
				*(this->pos + i) = *(napis + i);
				i++;
			}
			*(this->pos + i) = '\0';
		}
		next = nullptr;
		prev = nullptr;
	}



	friend ostream& operator<<(ostream& str, Node n) {
		str << n.bukwa << (char)32 << n.pos;
		return str;
	}
};

class List {
public:
	Node * head, *tail;

	List() {
		head = nullptr;
		tail = nullptr;
		char* temp = new char[65];
		char b;
		while (!cin.eof()) {
			cin >> b >> temp;
			if(*temp=='L'||*temp=='R')
				this->push(new Node(b, temp));
			else {
				char* x = new char[65];
				cin >> x;
				this->push(new Node(b, new char('\0')));
				this->push(new Node(*temp, x));
			}
		}
	}

	List*  push(Node* n) {
		n->next = this->head;
		n->prev = NULL;
		if (this->head) {
			this->head->prev = n;
		}
		this->head = n;
		if (this->tail == NULL) {
			this->tail = n;
		}
		return this;
	}

	void sort(Node* first, Node* last, int level) {
		if (first == last)return;
		bool key = false;
		bool swap = false;
		Node *empty = first;
		Node *lpointer = first, *rpointer = last;
		while (lpointer != rpointer) {
			if (!swap)

				if (lpointer->pos[level] == '\0') {
					lpointer = lpointer->next;
					empty = empty->next;
				}
				else {
					swap = true;
					key = true;
				}
			else
				if (rpointer->pos[level] == '\0') {
					rpointer->swap(lpointer);
					swap = false;
				}
				else
					rpointer = rpointer->prev;
		}
		if (key) {
			swap = false;
			lpointer = empty;
			rpointer = last;
			while (lpointer != rpointer) {
				if (!swap)
					if (lpointer->pos[level] == 'L')
						lpointer = lpointer->next;
					else
						swap = true;
				else
					if (rpointer->pos[level] == 'R')
						rpointer = rpointer->prev;
					else {
						rpointer->swap(lpointer);
						swap = false;
					}
			}
			level++;
			if ((lpointer == empty) || (rpointer == last))
				sort(empty, last, level);
			else {
				sort(empty, lpointer->prev, level);
				sort(rpointer, last, level);
			}

		}
	}


	friend ostream& operator<<(ostream& str, List l) {
		Node *temp = l.head;
		while (temp) {
			str << *temp << '\n';
			temp = temp->next;
		}
		return str;
	}

};

int main() {
	char *temp = new char[67];
	char word[] = "fasds";
	temp = word;
 	//char *start = temp;
	//cout << temp;

	List* list = new List;

	//cout << *list->head; //<< endl << *list->head->next;
	//list->push(new Node('a', temp));
	cout << *list;
	system("pause");
	//    cout << "tail="<<*list->tail<<endl;
	//    cout << "head="<<*list->head<<endl;
	//    list->sort(list->head,list->tail,0);
	//    cout << *list;
	return 0;
}