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

typedef struct DoublyLinkedList {
  int val;
  struct DoublyLinkedList *prev, *next;
} DLL;

void InitializeNode(DLL **head);
void InsertNode(DLL *head, int targetValue);
void DeleteNodeByKey(DLL *head, int targetValue);
void DeleteNode(DLL *head, DLL *targetNode);
DLL *SearchValueFirstOccurrence(DLL *head, int targetValue);
void DeleteFirstNode(DLL *head);
void DeleteLastNode(DLL *head);
void PrintLinkedList(DLL *head);
void FreeLinkedListSpace(DLL *head);

int main() {
  int n, value;
  char cmd[30];
  DLL *nil;

  InitializeNode(&nil);

  scanf("%d", &n);

  for (int i = 0; i < n; i++) {
    scanf("%s", cmd);

    if (cmd[0] == 'i') {
      if (scanf("%d", &value) != 1) {
        fprintf(stderr, "ERROR! Expect a number following 'insert' command.\n");
        exit(-1);
      }

      InsertNode(nil, value);
    } else if (cmd[0] == 'd') {
      if (cmd[6] == 'F') {
        DeleteFirstNode(nil);
      } else if (cmd[6] == 'L') {
        DeleteLastNode(nil);
      } else {
        if (scanf("%d", &value) != 1) {
          fprintf(stderr,
                  "ERROR! Expect a number following 'delete' command.\n");
          exit(-1);
        }

        DeleteNodeByKey(nil, value);
      }
    } else {
      fprintf(stderr, "ERROR! Invalid command!\n");
      exit(-1);
    }
  }

  PrintLinkedList(nil);
  FreeLinkedListSpace(nil);
  nil = NULL;

  return 0;
}

void InitializeNode(DLL **head) {
  /* allocation might change the address of **head, so double pointers
   * or reference to pointer (in C++) should be used here */
  *head = (DLL *)calloc(1, sizeof(DLL));
  if (!*head) {
    fprintf(stderr, "ERROR! Cannot allocate nil structure!\n");
    exit(-1);
  }

  (*head)->prev = *head;
  (*head)->next = *head;
}

void InsertNode(DLL *head, int targetValue) {
  DLL *newNode;
  newNode = (DLL *)calloc(1, sizeof(DLL));
  if (!newNode) {
    fprintf(stderr, "ERROR! Cannot allocate newNode structure!\n");
    exit(-1);
  }

  newNode->val = targetValue;
  newNode->next = head->next;
  head->next->prev = newNode;
  head->next = newNode;
  newNode->prev = head;
}

void DeleteNodeByKey(DLL *head, int targetValue) {
  DeleteNode(head, SearchValueFirstOccurrence(head, targetValue));
}

void DeleteNode(DLL *head, DLL *targetNode) {
  if (head == targetNode) {
    return;
  }

  targetNode->prev->next = targetNode->next;
  targetNode->next->prev = targetNode->prev;

  free(targetNode);
}

DLL *SearchValueFirstOccurrence(DLL *head, int targetValue) {
  DLL *targetNode;

  targetNode = head->next;

  while (targetNode != head && targetNode->val != targetValue) {
    targetNode = targetNode->next;
  }

  return targetNode;
}

void DeleteFirstNode(DLL *head) { DeleteNode(head, head->next); }

void DeleteLastNode(DLL *head) { DeleteNode(head, head->prev); }

void PrintLinkedList(DLL *head) {
  DLL *tmpNode;
  tmpNode = head->next;

  while (tmpNode != head) {
    if (tmpNode->prev != head) {
      fprintf(stdout, " ");
    }
    fprintf(stdout, "%d", tmpNode->val);
    tmpNode = tmpNode->next;
  }
  fprintf(stdout, "\n");
}

void FreeLinkedListSpace(DLL *head) {
  while (head != head->next) {
    DeleteFirstNode(head);
  }
  head->next = head->prev = NULL;
  free(head);
}


Measured memory_bytes: 33108