import java.io.*;

// A single node in the doubly linked list
class DLLNode {
    int data;
    DLLNode prev;  // Pointer to the previous node
    DLLNode next;  // Pointer to the next node

    public DLLNode() {
        prev = next = null;
        data = 0;
    }
}

// Doubly Linked List with full insertion, deletion, search, and display
class DoublyLinkedList {
    DLLNode start;    // First node in the list
    DLLNode last;     // Last node in the list
    DLLNode current;  // Helper pointer for traversal

    // Creates the first node when the list is empty
    private void createList(int value) {
        DLLNode newNode = new DLLNode();
        newNode.data = value;
        start = last = newNode;
    }

    // Inserts a new node at the beginning of the list
    public void insertAtFirst(int value) {
        if (start == null) {
            createList(value);
        } else {
            DLLNode newNode = new DLLNode();
            newNode.data = value;
            start.prev = newNode;  // Old start's prev now points to new node
            newNode.next = start;  // New node's next points to old start
            start = newNode;       // Update start to new node
        }
    }

    // Inserts a new node at the end of the list
    public void insertAtLast(int value) {
        if (start == null) {
            createList(value);
        } else {
            DLLNode newNode = new DLLNode();
            newNode.data = value;
            last.next = newNode;   // Old last's next points to new node
            newNode.prev = last;   // New node's prev points to old last
            last = newNode;        // Update last to new node
        }
    }

    // Inserts a new node after the node at the given 1-based position
    public void insertAfter(int value, int position) {
        if (start == null) {
            createList(value);
            return;
        }
        if (position <= 0) {
            System.out.println("Invalid position");
            return;
        }
        int index = 1;
        current = start;
        while (current != null) {
            if (index == position) {
                DLLNode newNode = new DLLNode();
                newNode.data = value;
                newNode.next = current.next;
                if (current.next != null) current.next.prev = newNode;
                newNode.prev = current;
                current.next = newNode;
                return;
            }
            current = current.next;
            index++;
        }
        System.out.println("Position out of range");
    }

    // Inserts a new node before the node at the given 1-based position
    public void insertBefore(int value, int position) {
        if (start == null) {
            createList(value);
            return;
        }
        if (position <= 1) {
            insertAtFirst(value);
            return;
        }
        int index = 1;
        current = start;
        while (current != null) {
            if (index == position - 1) {
                DLLNode newNode = new DLLNode();
                newNode.data = value;
                newNode.next = current.next;
                if (current.next != null) current.next.prev = newNode;
                newNode.prev = current;
                current.next = newNode;
                return;
            }
            current = current.next;
            index++;
        }
        System.out.println("Position out of range");
    }

    // Searches for a value and returns its 1-based position, or -1 if not found
    public int search(int value) {
        current = start;
        int position = 1;
        while (current != null) {
            if (current.data == value) return position;
            current = current.next;
            position++;
        }
        return -1;
    }

    // Displays the list from start to end (forward direction)
    public void displayForward() {
        current = start;
        System.out.print("Forward: ");
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    // Displays the list from end to start (reverse direction)
    public void displayReverse() {
        current = last;
        System.out.print("Reverse: ");
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.prev;
        }
        System.out.println();
    }

    // Removes and returns the first node's value
    public int deleteFirst() {
        if (start == null) {
            System.out.println("List is empty");
            return 0;
        }
        int value = start.data;
        start = start.next;
        if (start != null) start.prev = null;
        else last = null;
        return value;
    }

    // Removes and returns the last node's value
    public int deleteLast() {
        if (start == null) {
            System.out.println("List is empty");
            return 0;
        }
        int value = last.data;
        if (last.prev != null) {
            last.prev.next = null;
            last = last.prev;
        } else {
            start = last = null;
        }
        return value;
    }

    // Removes and returns the node at the given 1-based position
    public int deleteAt(int position) {
        if (start == null) {
            System.out.println("List is empty");
            return 0;
        }
        if (position <= 0) {
            System.out.println("Invalid position");
            return 0;
        }
        current = start;
        int index = 1;
        while (current != null) {
            if (index == position) {
                int value = current.data;
                if (current.prev != null) current.prev.next = current.next;
                else start = current.next;
                if (current.next != null) current.next.prev = current.prev;
                else last = current.prev;
                return value;
            }
            current = current.next;
            index++;
        }
        System.out.println("Position out of range");
        return 0;
    }
}

public class DLLDemo {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        DoublyLinkedList dll = new DoublyLinkedList();
        int choice;

        do {
            System.out.println();
            System.out.println("--- Doubly Linked List Menu ---");
            System.out.println("1. Insert");
            System.out.println("2. Remove");
            System.out.println("3. Display list");
            System.out.println("4. Search");
            System.out.println("5. Exit");
            System.out.print("Select option: ");
            choice = Integer.parseInt(reader.readLine());

            switch (choice) {
                case 1:
                    System.out.println("1. Insert at first");
                    System.out.println("2. Insert at last");
                    System.out.println("3. Insert after position");
                    System.out.println("4. Insert before position");
                    System.out.print("Select: ");
                    int insertChoice = Integer.parseInt(reader.readLine());
                    System.out.print("Enter element: ");
                    int insertValue = Integer.parseInt(reader.readLine());
                    if (insertChoice == 1) {
                        dll.insertAtFirst(insertValue);
                    } else if (insertChoice == 2) {
                        dll.insertAtLast(insertValue);
                    } else if (insertChoice == 3) {
                        System.out.print("Enter position: ");
                        int pos = Integer.parseInt(reader.readLine());
                        dll.insertAfter(insertValue, pos);
                    } else if (insertChoice == 4) {
                        System.out.print("Enter position: ");
                        int pos = Integer.parseInt(reader.readLine());
                        dll.insertBefore(insertValue, pos);
                    }
                    break;
                case 2:
                    System.out.println("1. Delete first");
                    System.out.println("2. Delete last");
                    System.out.println("3. Delete at position");
                    System.out.print("Select: ");
                    int deleteChoice = Integer.parseInt(reader.readLine());
                    if (deleteChoice == 1) {
                        System.out.println("Deleted: " + dll.deleteFirst());
                    } else if (deleteChoice == 2) {
                        System.out.println("Deleted: " + dll.deleteLast());
                    } else if (deleteChoice == 3) {
                        System.out.print("Enter position: ");
                        int pos = Integer.parseInt(reader.readLine());
                        System.out.println("Deleted: " + dll.deleteAt(pos));
                    }
                    break;
                case 3:
                    System.out.println("1. Forward display");
                    System.out.println("2. Reverse display");
                    System.out.print("Select: ");
                    int displayChoice = Integer.parseInt(reader.readLine());
                    if (displayChoice == 1) dll.displayForward();
                    else dll.displayReverse();
                    break;
                case 4:
                    System.out.print("Enter element to search: ");
                    int searchValue = Integer.parseInt(reader.readLine());
                    int position = dll.search(searchValue);
                    System.out.println(position != -1
                        ? "Element found at position: " + position
                        : "Element not found");
                    break;
                case 5:
                    System.out.println("Exiting...");
                    break;
            }
        } while (choice != 5);
    }
}