import java.util.*;

class Node {
   int data;
   Node prev;
   Node next;
   
   public Node(int data) {
      this.data = data;
      this.prev = null;
      this.next = null;

   }
}

class DoublyLinkedListCalaycay {
    Node head;
    Node tail;

    // Constructor to initialize an empty list.
    public DoublyLinkedListCalaycay() {
        head = null;
        tail = null;
    }
    // Add a new node to the head of the list.
    public void addToHead(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
        System.out.println("Added " + data + " to the head.");
    }
    // Add a new node to the tail of the list.
    public void addToTail(int data) {
        Node newNode = new Node(data);
        if (tail == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
        System.out.println("Added " + data + " to the tail.");
    }
    // Print the data in the head node.
    public void printHead() {
        if (head != null) {
            System.out.println("Head: " + head.data);
        } else {
            System.out.println("List is empty.");
        }
    }
    // Print the data in the tail node.
    public void printTail() {
        if (tail != null) {
            System.out.println("Tail: " + tail.data);
        } else {
            System.out.println("List is empty.");
        }
    }
    // Print the data in the list from head to tail.
    public void printForward() {
        Node current = head;
        System.out.print("Forward: ");
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
    // Print the data in the list from tail to head.
    public void printBackward() {
        Node current = tail;
        System.out.print("Backward: ");
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.prev;
        }
        System.out.println();
    }
    // Remove the node from the head of the list.
    public void removeFromHead() {
        if (head != null) {
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                head = head.next;
                head.prev = null;
            }
            System.out.println("Removed from head.");
        } else {
            System.out.println("List is empty.");
        }
    }
    // Remove the node from the tail of the list.
    public void removeFromTail() {
        if (tail != null) {
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                tail = tail.prev;
                tail.next = null;
            }
            System.out.println("Removed from tail.");
        } else {
            System.out.println("List is empty.");
        }
    }
    // Insert a new node after a specific item.
    public void insertNodeAfter(int searchItem, int itemToInsert) {
        Node newNode = new Node(itemToInsert);
        Node current = head;
        while (current != null) {
            if (current.data == searchItem) {
                newNode.prev = current;
                newNode.next = current.next;
                if (current.next != null) {
                    current.next.prev = newNode;
                } else {
                    tail = newNode;
                }
                current.next = newNode;
                System.out.println("Inserted " + itemToInsert + " after " + searchItem + ".");
                return;
            }
            current = current.next;
        }
        System.out.println(searchItem + " not found in the list.");
    }
    // Remove a specific node from the list.
    public void removeNode(int itemToRemove) {
        Node current = head;
        while (current != null) {
            if (current.data == itemToRemove) {
                if (current == head) {
                    removeFromHead();
                } else if (current == tail) {
                    removeFromTail();
                } else {
                    current.prev.next = current.next;
                    current.next.prev = current.prev;
                    System.out.println("Removed " + itemToRemove + " from the list.");
                }
                return;
            }
            current = current.next;
        }
        System.out.println(itemToRemove + " not found in the list.");
    }
}

import java.util.*;

public class DoublyLinkedListDemo {
    public static void main(String[] args) {
        DoublyLinkedListCalaycay list = new DoublyLinkedListCalaycay();
        Scanner scanner = new Scanner(System.in);
        
        while (true) {
            System.out.println("Doubly Linked List Operations:");
            System.out.println("1 - Add to Head");
            System.out.println("2 - Add to Tail");
            System.out.println("3 - Print Head");
            System.out.println("4 - Print Tail");
            System.out.println("5 - Print Forward");
            System.out.println("6 - Print Backward");
            System.out.println("7 - Remove from Head");
            System.out.println("8 - Remove from Tail");
            System.out.println("9 - Insert Node After");
            System.out.println("10 - Remove Node");
            System.out.println("11 - Quit");
            System.out.print("Enter your choice (1-11): ");

            int choice = scanner.nextInt();

            switch (choice) {

                case 1:
                    System.out.print("Enter value to add to the head: ");
                    int data = scanner.nextInt();
                    list.addToHead(data);
                    break;
                case 2:
                    System.out.print("Enter value to add to the tail: ");
                    data = scanner.nextInt();
                    list.addToTail(data);
                    break;
                case 3:
                    list.printHead();
                    break;
                case 4:
                    list.printTail();
                    break;
                case 5:
                    list.printForward();
                    break;
                case 6:
                    list.printBackward();
                    break;
                case 7:
                    list.removeFromHead();
                    break;
                case 8:
                    list.removeFromTail();
                    break;
                case 9:
                    System.out.print("Enter the item to search for: ");
                    int searchItem = scanner.nextInt();
                    System.out.print("Enter the item to insert after: ");
                    int itemToInsert = scanner.nextInt();
                    list.insertNodeAfter(searchItem, itemToInsert);
                    break;
                case 10:
                    System.out.print("Enter the item to remove: ");
                    int itemToRemove = scanner.nextInt();
                    list.removeNode(itemToRemove);
                    break;
                case 11:
                    System.out.println("Exiting...");
                    scanner.close();
                    System.exit(0);
                    
                default:
                    System.out.println("Invalid choice. Please enter a valid option.");
            }
        }
    }
}