

from typing import Any






class 						__magic_name__    :


 def __init__(						self		: Dict			,						lowerCAmelCase__		: Any    )    ->      int:
   UpperCAmelCase					      =  data
   UpperCAmelCase					      =  None


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






class 						__magic_name__    :


 def __init__(						self		: Optional[int]    )    ->      List[str]:
   UpperCAmelCase					      =  None


 def __iter__(						self		: str    )    ->      Any:
   UpperCAmelCase					      =  self.head
   while node:
     yield node.data
     UpperCAmelCase					      =  node.next


 def __len__(						self		: Union[str, Any]    )    ->      int:
   return sum(1 for _ in self    )


 def __repr__(						self		: int    )    ->      str:
   return "->".join([str(lowerCAmelCase__    ) for item in self]    )


 def __getitem__(						self		: List[Any]			,						lowerCAmelCase__		: 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		: Optional[int]			,						lowerCAmelCase__		: int			,						lowerCAmelCase__		: Any    )    ->      None:
   if not 0 <= index < len(self    ):
     raise ValueError("list index out of range."    )
   UpperCAmelCase					      =  self.head
   for _ in range(lowerCAmelCase__    ):
     UpperCAmelCase					      =  current.next
   UpperCAmelCase					      =  data


 def _UpperCamelCase	(						self		: int			,						lowerCAmelCase__		: Any    )    ->      None:
   self.insert_nth(len(self    )			,						lowerCAmelCase__    )


 def _UpperCamelCase	(						self		: Optional[int]			,						lowerCAmelCase__		: Any    )    ->      None:
   self.insert_nth(0			,						lowerCAmelCase__    )


 def _UpperCamelCase	(						self		: int			,						lowerCAmelCase__		: int			,						lowerCAmelCase__		: Any    )    ->      None:
   if not 0 <= index <= len(self    ):
     raise IndexError("list index out of range"    )
   UpperCAmelCase					      =  Node(lowerCAmelCase__    )
   if self.head is None:
     UpperCAmelCase					      =  new_node
   elif index == 0:
     UpperCAmelCase					      =  self.head  # link new_node to head
     UpperCAmelCase					      =  new_node
   else:
     UpperCAmelCase					      =  self.head
     for _ in range(index - 1    ):
       UpperCAmelCase					      =  temp.next
     UpperCAmelCase					      =  temp.next
     UpperCAmelCase					      =  new_node


 def _UpperCamelCase	(						self		: int    )    ->      None:  # print every node data
   print(self    )


 def _UpperCamelCase	(						self		: Dict    )    ->      Any:
   return self.delete_nth(0    )


 def _UpperCamelCase	(						self		: Optional[int]    )    ->      Any:  # delete from tail
   return self.delete_nth(len(self    ) - 1    )


 def _UpperCamelCase	(						self		: Optional[int]			,						lowerCAmelCase__		: int = 0    )    ->      Any:
   if not 0 <= index <= len(self    ) - 1:  # test if index is valid
     raise IndexError("List index out of range."    )
   UpperCAmelCase					      =  self.head  # default first node
   if index == 0:
     UpperCAmelCase					      =  self.head.next
   else:
     UpperCAmelCase					      =  self.head
     for _ in range(index - 1    ):
       UpperCAmelCase					      =  temp.next
     UpperCAmelCase					      =  temp.next
     UpperCAmelCase					      =  temp.next.next
   return delete_node.data


 def _UpperCamelCase	(						self		: Any    )    ->      bool:
   return self.head is None


 def _UpperCamelCase	(						self		: Union[str, Any]    )    ->      None:
   UpperCAmelCase					      =  None
   UpperCAmelCase					      =  self.head

   while current:
     # Store the current node's next node.
     UpperCAmelCase					      =  current.next
     # Make the current node's next point backwards
     UpperCAmelCase					      =  prev
     # Make the previous node be the current node
     UpperCAmelCase					      =  current
     # Make the current node the next node (to progress iteration)
     UpperCAmelCase					      =  next_node
   # Return prev in order to put the head at the end
   UpperCAmelCase					      =  prev

def      _lowerCAmelCase(	):
  UpperCAmelCase					      =  LinkedList()
  assert linked_list.is_empty() is True
  assert str(__A			) == ""

  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(__A			) == i
    linked_list.insert_nth(__A   ,       i + 1			)
  assert str(__A			) == "->".join(str(__A			) for i in range(1   ,       11			)			)

  linked_list.insert_head(0			)
  linked_list.insert_tail(11			)
  assert str(__A			) == "->".join(str(__A			) 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(__A			) == 9
  assert str(__A			) == "->".join(str(__A			) 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			):
    UpperCAmelCase					      =  -i
  assert all(linked_list[i] == -i for i in range(0   ,       9			)			) is True

  linked_list.reverse()
  assert str(__A			) == "->".join(str(__A			) for i in range(-8   ,       1			)			)
def      _lowerCAmelCase(	):
  UpperCAmelCase					      =  [
      -9,
      100,
      Node(77345112			),
      "dlrow olleH",
      7,
      5555,
      0,
      -192.55555,
      "Hello, world!",
      77.9,
      Node(10			),
      None,
      None,
      12.20,
  ]
  UpperCAmelCase					      =  LinkedList()

  for i in test_input:
    linked_list.insert_tail(__A			)

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

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

  # Delete the tail
  UpperCAmelCase					      =  linked_list.delete_tail()
  assert result == 12.2
  assert (
      str(__A			) == "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
  UpperCAmelCase					      =  linked_list.delete_nth(10			)
  assert result is None
  assert (
      str(__A			) == "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(__A			)
      == "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(__A			)
  assert (
      str(__A			)
      == "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(__A			)
      == "None->None->Node(10)->77.9->Hello, world!->-192.55555->0->5555->"
      "7->dlrow olleH->Node(77345112)->100->Node(Hello again, world!)"
  )
def      _lowerCAmelCase(	):
  from doctest import testmod

  testmod()

  UpperCAmelCase					      =  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(__A			)
  print("\nReading/changing Node data using indexing:"			)
  print(F"Element at Position 1: {linked_list[1]}"			)
  UpperCAmelCase					      =  input("Enter New Value: "			).strip()
  print("New list:"			)
  print(__A			)
  print(F"length of linked_list is : {len(__A			)}"			)


if __name__ == "__main__":
      main()






def      _lowerCAmelCase(	__A   ,       __A			):
  return (pointa[0] - pointa[0]) ** 2 + (pointa[1] - pointa[1]) ** 2
def      _lowerCAmelCase(	__A   ,       __A=0			):
  return sorted(__A   ,       key=lambda __A			: x[column]			)
def      _lowerCAmelCase(	__A   ,       __A   ,       __A=float("inf"			)			):

  for i in range(points_counts - 1			):
    for j in range(i + 1   ,       __A			):
      UpperCAmelCase					      =  euclidean_distance_sqr(points[i]   ,       points[j]			)
      if current_dis < min_dis:
        UpperCAmelCase					      =  current_dis
  return min_dis
def      _lowerCAmelCase(	__A   ,       __A   ,       __A=float("inf"			)			):

  for i in range(min(6   ,       points_counts - 1			)   ,       __A			):
    for j in range(max(0   ,       i - 6			)   ,       __A			):
      UpperCAmelCase					      =  euclidean_distance_sqr(points[i]   ,       points[j]			)
      if current_dis < min_dis:
        UpperCAmelCase					      =  current_dis
  return min_dis
def      _lowerCAmelCase(	__A   ,       __A   ,       __A			):

  # base case
  if points_counts <= 3:
    return dis_between_closest_pair(__A   ,       __A			)

  # recursion
  UpperCAmelCase					      =  points_counts // 2
  UpperCAmelCase					      =  closest_pair_of_points_sqr(
      __A   ,       points_sorted_on_y[:mid]   ,       __A			)
  UpperCAmelCase					      =  closest_pair_of_points_sqr(
      __A   ,       points_sorted_on_y[mid:]   ,       points_counts - mid			)
  UpperCAmelCase					      =  min(__A   ,       __A			)
  UpperCAmelCase					      =  []
  for point in points_sorted_on_x:
    if abs(point[0] - points_sorted_on_x[mid][0]			) < closest_pair_dis:
      cross_strip.append(__A			)

  UpperCAmelCase					      =  dis_between_closest_in_strip(
      __A   ,       len(__A			)   ,       __A			)
  return min(__A   ,       __A			)
def      _lowerCAmelCase(	__A   ,       __A			):
  UpperCAmelCase					      =  column_based_sort(__A   ,       column=0			)
  UpperCAmelCase					      =  column_based_sort(__A   ,       column=1			)
  return (
      closest_pair_of_points_sqr(
          __A   ,       __A   ,       __A			)
  ) ** 0.5


if __name__ == "__main__":
      lowerCAmelCase__       = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
      print("Distance:", closest_pair_of_points(points, len(points)))



