#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

typedef int Key_t;
typedef struct tagNode_t Node_t;
typedef struct tagDoublyLinkedList_t DoublyLinkedList_t;
typedef enum tagCommand_e Command_e;

struct tagNode_t {
	Key_t key;
	Node_t* prev;
	Node_t* next;
};

struct tagDoublyLinkedList_t {
	Node_t* head;
	Node_t* tail;
};

enum tagCommand_e {
	INSERT = 0,
	DELETE,
	DELETE_FIRST,
	DELETE_LAST,
	UNDEFINED_COMMAND = 4
};

DoublyLinkedList_t  InterpretCommand(void);
DoublyLinkedList_t  DoublyLinkedList_CreateInstance(void);
Node_t* DoublyLinkedList_CreateNode(void);
DoublyLinkedList_t  DoublyLinkedList_Initalize(void);
void DoublyLinkedList_Insert(DoublyLinkedList_t* self, Key_t x);
void DoublyLinkedList_Delete(DoublyLinkedList_t* self, Key_t x);
void DoublyLinkedList_DeleteFirst(DoublyLinkedList_t* self);
void DoublyLinkedList_DeleteLast(DoublyLinkedList_t* self);
void DoublyLinkedList_PrintAll(DoublyLinkedList_t self);

Command_e ConvertCommand(char *command);

int main(void)
{
	DoublyLinkedList_t self = InterpretCommand();

	DoublyLinkedList_PrintAll(self);

	return 0;
}

DoublyLinkedList_t InterpretCommand(void)
{
	DoublyLinkedList_t self = DoublyLinkedList_CreateInstance();
	uint32_t numOfCommands;
	char buf[256];
	char  readLine[256];

	if (scanf("%255[^\n]%*[^\n]", buf) != 1) {
		exit(0);
	}

	numOfCommands = atoi(buf);

	for (uint32_t i=0;i < numOfCommands;i++) {

		char *c;
		scanf("%*c", c);

		if (scanf("%255[^\n]%*[^\n]", readLine) != 1) {
			exit(0);
		}

		char* commandStr;
		Key_t key;
		Command_e command;

		commandStr = strtok(readLine, " ");
		command = ConvertCommand(commandStr);

		switch(command) {
			case INSERT:
				commandStr = strtok(NULL, " ");
				key = (Key_t) atoi(commandStr);
				DoublyLinkedList_Insert(&self, key);
				break;
			case DELETE:
				commandStr = strtok(NULL, " ");
				key = (Key_t) atoi(commandStr);
				DoublyLinkedList_Delete(&self, key);
				break;
			case DELETE_FIRST:
				DoublyLinkedList_DeleteFirst(&self);
				break;
			case DELETE_LAST:
				DoublyLinkedList_DeleteLast(&self);
				break;
			default:
				exit(0);
		}
	}

	return self;
}

DoublyLinkedList_t  DoublyLinkedList_CreateInstance(void)
{
	DoublyLinkedList_t emptyList;

	emptyList.head = NULL;
	emptyList.tail = NULL;

	return emptyList;
}

Node_t* DoublyLinkedList_CreateNode(void)
{
	return (Node_t *)malloc(sizeof(Node_t));
}

void DoublyLinkedList_Insert(DoublyLinkedList_t* self, Key_t x)
{
	Node_t* node = DoublyLinkedList_CreateNode();

	node->key  = x;
	node->prev = NULL;
	node->next = self->head;

	if (self->head != NULL) {
		self->head->prev = node;
	}

	self->head = node;

	if (self->tail == NULL) {
		self->tail = node;
	}
}

void DoublyLinkedList_Delete(DoublyLinkedList_t* self, Key_t x)
{
	Node_t* node = self->head;

	while(node != NULL) {
		if (node->key == x && node->prev != NULL && node->next != NULL) {
			node->prev->next = node->next;
			node->next->prev = node->prev;
			free(node);
			return;
		} else if (node->key == x && node->next != NULL) {
			self->head = node->next;
			node->next->prev = NULL;
			free(node);
			return;
		} else if (node->key == x && node->prev != NULL) {
			self->tail = node->prev;
			node->prev->next = NULL;
			free(node);
			return;
		}

		node = node->next;
	}
}

void DoublyLinkedList_DeleteFirst(DoublyLinkedList_t* self)
{
	Node_t* node = self->head;

	if (node->next != NULL) {
		node->next->prev = NULL;
		self->head = node->next;
	} else {
		self->head = NULL;
		self->tail = NULL;
	}

	free(node);
}

void DoublyLinkedList_DeleteLast(DoublyLinkedList_t* self)
{
	Node_t* node = self->tail;

	if (node->prev != NULL) {
		node->prev->next = NULL;
		self->tail = node->prev;
	} else {
		self->head = NULL;
		self->tail = NULL;
	}

	free(node);
}

void DoublyLinkedList_PrintAll(DoublyLinkedList_t self)
{
	Node_t* node = self.head;

	while (node != NULL) {
		printf("%d", node->key);
		if (node->next != NULL) {
			printf(" ");
		}
		node = node->next;
	}

	printf("\n");
}

Command_e ConvertCommand(char *command)
{
	if (strcmp(command, "insert") == 0) {
		return INSERT;
	} else if (strcmp(command, "delete") == 0) {
		return DELETE;
	} else if (strcmp(command, "deleteFirst") == 0) {
		return DELETE_FIRST;
	} else if (strcmp(command, "deleteLast") == 0) {
		return DELETE_LAST;
	} else {
		exit(0);
	}

	return UNDEFINED_COMMAND;
}

