





from typing import Any

class    lowerCAmelCase							:
 def __init__(      self  :      int			,     UpperCAmelCase  :      Any	)			->	Dict:
     lowerCamelCase__    :      Optional[int]					 =		data
     lowerCamelCase__    :      str					 =		None







 def __repr__(      self  :      Any	)			->	str:
     return F"""Node({self.data})"""


class    lowerCAmelCase							:
 def __init__(      self  :      Tuple	)			->	Any:
     lowerCamelCase__    :      Optional[Any]					 =		None
 def __iter__(      self  :      Any	)			->	Any:
     lowerCamelCase__    :      Any					 =		self.head
     while node:
         yield node.data
         lowerCamelCase__    :      List[Any]					 =		node.next
 def __len__(      self  :      Optional[Any]	)			->	int:
     return sum(1 for _ in self	)
 def __repr__(      self  :      Tuple	)			->	str:
     return "->".join([str(UpperCAmelCase	) for item in self]	)
 def __getitem__(      self  :      str			,     UpperCAmelCase  :      int	)			->	Any:
     if not 0 <= index < len(self	):
         raise ValueError('list index out of range.'	)
     for i, node in enumerate(self	):
         if i == index:
             return node
     return None
 def __setitem__(      self  :      Any			,     UpperCAmelCase  :      int			,     UpperCAmelCase  :      Any	)			->	None:
     if not 0 <= index < len(self	):
         raise ValueError('list index out of range.'	)
     lowerCamelCase__    :      List[str]					 =		self.head
     for _ in range(UpperCAmelCase	):
         lowerCamelCase__    :      Any					 =		current.next
     lowerCamelCase__    :      Optional[int]					 =		data
 def      A_	(      self  :      Any			,     UpperCAmelCase  :      Any	)			->	None:
     self.insert_nth(len(self	)			,     UpperCAmelCase	)
 def      A_	(      self  :      List[str]			,     UpperCAmelCase  :      Any	)			->	None:
     self.insert_nth(0			,     UpperCAmelCase	)
 def      A_	(      self  :      Optional[Any]			,     UpperCAmelCase  :      int			,     UpperCAmelCase  :      Any	)			->	None:
     if not 0 <= index <= len(self	):
         raise IndexError('list index out of range'	)
     lowerCamelCase__    :      Union[str, Any]					 =		Node(UpperCAmelCase	)
     if self.head is None:
         lowerCamelCase__    :      Dict					 =		new_node
     elif index == 0:
         lowerCamelCase__    :      Dict					 =		self.head  # link new_node to head
         lowerCamelCase__    :      Optional[int]					 =		new_node
     else:
         lowerCamelCase__    :      Optional[int]					 =		self.head
         for _ in range(index - 1	):
             lowerCamelCase__    :      int					 =		temp.next
         lowerCamelCase__    :      int					 =		temp.next
         lowerCamelCase__    :      str					 =		new_node
 def      A_	(      self  :      Tuple	)			->	None:  # print every node data
     print(self	)
 def      A_	(      self  :      Optional[int]	)			->	Any:
     return self.delete_nth(0	)
 def      A_	(      self  :      Any	)			->	Any:  # delete from tail
     return self.delete_nth(len(self	) - 1	)
 def      A_	(      self  :      List[Any]			,     UpperCAmelCase  :      int = 0	)			->	Any:
     if not 0 <= index <= len(self	) - 1:  # test if index is valid
         raise IndexError('List index out of range.'	)
     lowerCamelCase__    :      Dict					 =		self.head  # default first node
     if index == 0:
         lowerCamelCase__    :      str					 =		self.head.next
     else:
         lowerCamelCase__    :      Tuple					 =		self.head
         for _ in range(index - 1	):
             lowerCamelCase__    :      Tuple					 =		temp.next
         lowerCamelCase__    :      List[str]					 =		temp.next
         lowerCamelCase__    :      Dict					 =		temp.next.next
     return delete_node.data
 def      A_	(      self  :      Optional[int]	)			->	bool:
     return self.head is None







 def      A_	(      self  :      Union[str, Any]	)			->	None:
     lowerCamelCase__    :      str					 =		None
     lowerCamelCase__    :      Optional[Any]					 =		self.head

     while current:
         # Store the current node's next node.
         lowerCamelCase__    :      Union[str, Any]					 =		current.next
         # Make the current node's next point backwards
         lowerCamelCase__    :      Dict					 =		prev
         # Make the previous node be the current node
         lowerCamelCase__    :      Optional[Any]					 =		current
         # Make the current node the next node (to progress iteration)
         lowerCamelCase__    :      str					 =		next_node
     # Return prev in order to put the head at the end
     lowerCamelCase__    :      List[str]					 =		prev


def        SCREAMING_SNAKE_CASE      (       )			->     None:
    lowerCamelCase__    :      Tuple					 =		LinkedList()
    assert linked_list.is_empty() is True
    assert str(_UpperCAmelCase ) == ""

    try:
        linked_list.delete_head()
        raise AssertionError  # This should not happen.
    except IndexError:
        assert True  # This should happen.

    try:
        linked_list.delete_tail()
        raise AssertionError  # This should not happen.
    except IndexError:
        assert True  # This should happen.

    for i in range(10 ):
        assert len(_UpperCAmelCase ) == i
        linked_list.insert_nth(_UpperCAmelCase						,	i + 1 )
    assert str(_UpperCAmelCase ) == "->".join(str(_UpperCAmelCase ) for i in range(1						,	11 ) )

    linked_list.insert_head(0 )
    linked_list.insert_tail(11 )
    assert str(_UpperCAmelCase ) == "->".join(str(_UpperCAmelCase ) for i in range(0						,	12 ) )

    assert linked_list.delete_head() == 0
    assert linked_list.delete_nth(9 ) == 10
    assert linked_list.delete_tail() == 11
    assert len(_UpperCAmelCase ) == 9
    assert str(_UpperCAmelCase ) == "->".join(str(_UpperCAmelCase ) for i in range(1						,	10 ) )

    assert all(linked_list[i] == i + 1 for i in range(0						,	9 ) ) is True

    for i in range(0						,	9 ):
        lowerCamelCase__    :      List[Any]					 =		-i
    assert all(linked_list[i] == -i for i in range(0						,	9 ) ) is True

    linked_list.reverse()
    assert str(_UpperCAmelCase ) == "->".join(str(_UpperCAmelCase ) for i in range(-8						,	1 ) )


def        SCREAMING_SNAKE_CASE      (       )			->     None:
    lowerCamelCase__    :      Union[str, Any]					 =		[
        -9,
        100,
        Node(7734_5112 ),
        'dlrow olleH',
        7,
        5555,
        0,
        -192.55_555,
        'Hello, world!',
        77.9,
        Node(10 ),
        None,
        None,
        12.20,
    ]
    lowerCamelCase__    :      List[Any]					 =		LinkedList()

    for i in test_input:
        linked_list.insert_tail(_UpperCAmelCase )

    # Check if it's empty or not
    assert linked_list.is_empty() is False
    assert (
        str(_UpperCAmelCase ) == "-9->100->Node(77345112)->dlrow olleH->7->5555->0->"
        "-192.55555->Hello, world!->77.9->Node(10)->None->None->12.2"
    )

    # Delete the head
    lowerCamelCase__    :      str					 =		linked_list.delete_head()
    assert result == -9
    assert (
        str(_UpperCAmelCase ) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
        "Hello, world!->77.9->Node(10)->None->None->12.2"
    )

    # Delete the tail
    lowerCamelCase__    :      List[Any]					 =		linked_list.delete_tail()
    assert result == 12.2
    assert (
        str(_UpperCAmelCase ) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
        "Hello, world!->77.9->Node(10)->None->None"
    )

    # Delete a node in specific location in linked list
    lowerCamelCase__    :      Any					 =		linked_list.delete_nth(10 )
    assert result is None
    assert (
        str(_UpperCAmelCase ) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
        "Hello, world!->77.9->Node(10)->None"
    )

    # Add a Node instance to its head
    linked_list.insert_head(Node('Hello again, world!' ) )
    assert (
        str(_UpperCAmelCase )
        == "Node(Hello again, world!)->100->Node(77345112)->dlrow olleH->"
        "7->5555->0->-192.55555->Hello, world!->77.9->Node(10)->None"
    )

    # Add None to its tail
    linked_list.insert_tail(_UpperCAmelCase )
    assert (
        str(_UpperCAmelCase )
        == "Node(Hello again, world!)->100->Node(77345112)->dlrow olleH->"
        "7->5555->0->-192.55555->Hello, world!->77.9->Node(10)->None->None"
    )

    # Reverse the linked list
    linked_list.reverse()
    assert (
        str(_UpperCAmelCase )
        == "None->None->Node(10)->77.9->Hello, world!->-192.55555->0->5555->"
        "7->dlrow olleH->Node(77345112)->100->Node(Hello again, world!)"
    )


def        SCREAMING_SNAKE_CASE      (       )			->     Any:
    from doctest import testmod

    testmod()

    lowerCamelCase__    :      str					 =		LinkedList()
    linked_list.insert_head(input('Inserting 1st at head ' ).strip() )
    linked_list.insert_head(input('Inserting 2nd at head ' ).strip() )
    print('\nPrint list:' )
    linked_list.print_list()
    linked_list.insert_tail(input('\nInserting 1st at tail ' ).strip() )
    linked_list.insert_tail(input('Inserting 2nd at tail ' ).strip() )
    print('\nPrint list:' )
    linked_list.print_list()
    print('\nDelete head' )
    linked_list.delete_head()
    print('Delete tail' )
    linked_list.delete_tail()
    print('\nPrint list:' )
    linked_list.print_list()
    print('\nReverse linked list' )
    linked_list.reverse()
    print('\nPrint list:' )
    linked_list.print_list()
    print('\nString representation of linked list:' )
    print(_UpperCAmelCase )
    print('\nReading/changing Node data using indexing:' )
    print(F"""Element at Position 1: {linked_list[1]}""" )
    lowerCamelCase__    :      int					 =		input('Enter New Value: ' ).strip()
    print('New list:' )
    print(_UpperCAmelCase )
    print(F"""length of linked_list is : {len(_UpperCAmelCase )}""" )


if __name__ == "__main__":
    main()












from __future__ import annotations


def        SCREAMING_SNAKE_CASE      (       _UpperCAmelCase						,	_UpperCAmelCase )			->     list[tuple[int, int]]:
    lowerCamelCase__ ,							lowerCamelCase__    :      Union[str, Any]					 =		position
    lowerCamelCase__    :      Optional[Any]					 =		[
        (y + 1, x + 2),
        (y - 1, x + 2),
        (y + 1, x - 2),
        (y - 1, x - 2),
        (y + 2, x + 1),
        (y + 2, x - 1),
        (y - 2, x + 1),
        (y - 2, x - 1),
    ]
    lowerCamelCase__    :      Dict					 =		[]

    for position in positions:
        lowerCamelCase__ ,							lowerCamelCase__    :      Optional[int]					 =		position
        if 0 <= y_test < n and 0 <= x_test < n:
            permissible_positions.append(_UpperCAmelCase )

    return permissible_positions


def        SCREAMING_SNAKE_CASE      (       _UpperCAmelCase )			->     bool:
    return not any(elem == 0 for row in board for elem in row )


def        SCREAMING_SNAKE_CASE      (       _UpperCAmelCase						,	_UpperCAmelCase						,	_UpperCAmelCase )			->     bool:

    if is_complete(_UpperCAmelCase ):
        return True

    for position in get_valid_pos(_UpperCAmelCase						,	len(_UpperCAmelCase ) ):
        lowerCamelCase__ ,							lowerCamelCase__    :      Optional[int]					 =		position

        if board[y][x] == 0:
            lowerCamelCase__    :      List[Any]					 =		curr + 1
            if open_knight_tour_helper(_UpperCAmelCase						,	_UpperCAmelCase						,	curr + 1 ):
                return True
            lowerCamelCase__    :      Optional[Any]					 =		0

    return False


def        SCREAMING_SNAKE_CASE      (       _UpperCAmelCase )			->     list[list[int]]:
    lowerCamelCase__    :      Any					 =		[[0 for i in range(_UpperCAmelCase )] for j in range(_UpperCAmelCase )]

    for i in range(_UpperCAmelCase ):
        for j in range(_UpperCAmelCase ):
            lowerCamelCase__    :      Optional[int]					 =		1
            if open_knight_tour_helper(_UpperCAmelCase						,	(i, j)						,	1 ):
                return board
            lowerCamelCase__    :      Optional[Any]					 =		0

    lowerCamelCase__    :      Any					 =		F"""Open Kight Tour cannot be performed on a board of size {n}"""
    raise ValueError(_UpperCAmelCase )


if __name__ == "__main__":
    import doctest

    doctest.testmod()





