import java.io.*;

// A single node in the singly linked list
class SLLNode {
    int data;
    SLLNode next;  // Pointer to the next node; null if this is the last node

    public SLLNode(int value) {
        data = value;
        next = null;
    }
}

// Singly Linked List with insert, remove, search, and display operations
class SinglyLinkedList {
    SLLNode start = null;  // Head node; null if the list is empty

    public boolean isEmpty() {
        return start == null;
    }

    // Inserts a new node at the beginning of the list
    public void insertFirst(int value) {
        SLLNode newNode = new SLLNode(value);
        if (isEmpty()) {
            start = newNode;
        } else {
            newNode.next = start;  // New node points to old head
            start = newNode;       // Update head to new node
        }
    }

    // Inserts a new node at the end of the list
    public void insertLast(int value) {
        SLLNode newNode = new SLLNode(value);
        if (isEmpty()) {
            start = newNode;
        } else {
            SLLNode current = start;
            while (current.next != null) {
                current = current.next;  // Traverse to the last node
            }
            current.next = newNode;
        }
    }

    // Inserts a new node at the given 1-based position
    public void insertAt(int value, int position) {
        if (isEmpty() || position <= 1) {
            insertFirst(value);
            return;
        }
        SLLNode current = start;
        int index = 1;
        while (current != null) {
            if (index == position - 1) {
                SLLNode newNode = new SLLNode(value);
                newNode.next = current.next;
                current.next = newNode;
                return;
            }
            current = current.next;
            index++;
        }
        System.out.println("Position out of range - inserting at end");
        insertLast(value);
    }

    // Removes and returns the first element
    public int removeFirst() {
        if (isEmpty()) {
            System.out.println("List is empty - nothing to remove");
            return 0;
        }
        int value = start.data;
        start = start.next;
        return value;
    }

    // Removes and returns the last element
    public int removeLast() {
        if (isEmpty()) {
            System.out.println("List is empty - nothing to remove");
            return 0;
        }
        if (start.next == null) {
            int value = start.data;
            start = null;
            return value;
        }
        SLLNode current = start;
        while (current.next.next != null) {
            current = current.next;  // Stop at second-to-last node
        }
        int value = current.next.data;
        current.next = null;
        return value;
    }

    // Removes and returns the element at the given 1-based position
    public int removeAt(int position) {
        if (isEmpty()) {
            System.out.println("List is empty - nothing to remove");
            return 0;
        }
        if (position <= 1) return removeFirst();

        SLLNode current = start;
        int index = 0;
        while (current != null) {
            if (index == position - 2) {
                if (current.next == null) {
                    System.out.println("Position out of range");
                    return 0;
                }
                int value = current.next.data;
                current.next = current.next.next;
                return value;
            }
            current = current.next;
            index++;
        }
        System.out.println("Position out of range");
        return 0;
    }

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

    // Displays all elements from head to tail
    public void display() {
        if (isEmpty()) {
            System.out.println("List is empty");
            return;
        }
        SLLNode current = start;
        System.out.print("List: ");
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

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

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

            switch (choice) {
                case 1:
                    System.out.println("1. Insert at position");
                    System.out.println("2. Insert at first");
                    System.out.println("3. Insert at last");
                    System.out.print("Enter choice: ");
                    int insertChoice = Integer.parseInt(reader.readLine());
                    System.out.print("Enter element: ");
                    int insertValue = Integer.parseInt(reader.readLine());
                    if (insertChoice == 1) {
                        System.out.print("Enter position: ");
                        int pos = Integer.parseInt(reader.readLine());
                        list.insertAt(insertValue, pos);
                    } else if (insertChoice == 2) {
                        list.insertFirst(insertValue);
                    } else if (insertChoice == 3) {
                        list.insertLast(insertValue);
                    }
                    break;
                case 2:
                    System.out.println("1. Remove first element");
                    System.out.println("2. Remove last element");
                    System.out.println("3. Remove element at position");
                    System.out.print("Enter choice: ");
                    int removeChoice = Integer.parseInt(reader.readLine());
                    if (removeChoice == 1) {
                        System.out.println("Removed: " + list.removeFirst());
                    } else if (removeChoice == 2) {
                        System.out.println("Removed: " + list.removeLast());
                    } else if (removeChoice == 3) {
                        System.out.print("Enter position: ");
                        int pos = Integer.parseInt(reader.readLine());
                        System.out.println("Removed: " + list.removeAt(pos));
                    }
                    break;
                case 3:
                    System.out.print("Enter element to search: ");
                    int searchValue = Integer.parseInt(reader.readLine());
                    int position = list.search(searchValue);
                    System.out.println(position != -1
                        ? "Element found at position: " + position
                        : "Element not found");
                    break;
                case 4:
                    list.display();
                    break;
                case 5:
                    System.out.println("Exiting...");
                    break;
            }
        } while (choice != 5);
    }
}