#include 
using namespace std;

struct node {
    int val;
    node * next;
    node * prev;
};

struct DLL {
    node *head;
    node *tail;
    
    void init() {
        head = NULL;
        tail = NULL;
    }
    void insertBegin(int x) {
        node *new_node = new node;
        new_node -> val = x;
        new_node->prev = NULL;
        new_node->next = NULL;
        if(head == NULL) {
            head = new_node;
            head->next = head;
            head->prev = head;
            tail = head;
        }
        else {
            new_node->next = head;
            head->prev = new_node;
            new_node->prev = tail;
            tail->next = new_node;
            head = new_node;
        }
    }
    void insertEnd(int x) {
        node *new_node = new node;
        new_node->val = x;
        new_node->next = NULL;
        new_node->prev = NULL;
        if(head == NULL) {
            head = new_node;
            head->next = head;
            head->prev = head;
            tail = head;
        }
        else {
            tail->next = new_node;
            new_node->prev = tail;
            new_node->next = head;
            head->prev = new_node;
            tail = new_node;
        }
    }
    
    void deleteBegin() {
        if(head != NULL) {
            if(head -> next == tail) {
                delete head;
                head = NULL;
                tail = NULL;
            }
            else {
                node *tmp = head;
                head = head->next;
                head->prev = tail;
                tail->next = head;
                delete tmp;
            }
        }
    }
    void deleteEnd() {
        if(head != NULL) {
            if(head -> next == tail) {
                delete head;
                head = NULL;
                tail = NULL;
            }
            else {
                node *tmp = tail;
                tail = tail->prev;
                tail->next = head;
                head->prev = tail;
                delete tmp;
            }
        }
    }
    void deleteAll() {
        while(head != NULL) {
            deleteBegin();
        }
    }
    void print() {
        node *tmp = head;
        for(int i = 0; i < 10; i++) {
            cout << tmp->val << " " ;
            tmp=tmp->next;
        }
        cout << endl;
        tmp = tail;
        for(int i= 0; i < 10; i++) {
            cout << tmp->val << " " ;
            tmp = tmp->prev;
        }
        cout << endl;
    }
    

};


int main() {
    DLL dll;
    dll.init();
    
    dll.insertBegin(2);
    dll.insertBegin(1);
    dll.insertEnd(3);
    dll.insertEnd(4);
    dll.insertEnd(5);
    
    
    dll.print();
    
   
    return 0;
}