




"""simple docstring"""







from typing import Any






class       SCREAMING_SNAKE_CASE__					:


						def __init__(							self				:			int						,						lowerCAmelCase				:			Any					):
										lowerCAmelCase  =				data
										lowerCAmelCase  =				None




						def __repr__(							self				:			str					):
										return f'''Node({self.data})'''






class       SCREAMING_SNAKE_CASE__					:


						def __init__(							self				:			str					):
										lowerCAmelCase  =				None


						def __iter__(							self				:			Any					):
										lowerCAmelCase  =				self.head
										while node:
														yield node.data
														lowerCAmelCase  =				node.next


						def __len__(							self				:			int					):
										return sum(1 for _ in self					)


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


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


						def   __lowercase (							self				:			Any						,						lowerCAmelCase				:			Any					):
										self.insert_nth(len(self					)						,						lowerCAmelCase					)


						def   __lowercase (							self				:			str						,						lowerCAmelCase				:			Any					):
										self.insert_nth(0						,						lowerCAmelCase					)


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


						def   __lowercase (							self				:			Optional[int]					):  # print every node data
										print(self					)


						def   __lowercase (							self				:			int					):
										return self.delete_nth(0					)


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


						def   __lowercase (							self				:			str						,						lowerCAmelCase				:			int = 0					):
										if not 0 <= index <= len(self					) - 1:  # test if index is valid
														raise IndexError("""List index out of range."""					)
										lowerCAmelCase  =				self.head  # default first node
										if index == 0:
														lowerCAmelCase  =				self.head.next
										else:
														lowerCAmelCase  =				self.head
														for _ in range(index - 1					):
																		lowerCAmelCase  =				temp.next
														lowerCAmelCase  =				temp.next
														lowerCAmelCase  =				temp.next.next
										return delete_node.data


						def   __lowercase (							self				:			Tuple					):
										return self.head is None




						def   __lowercase (							self				:			int					):
										lowerCAmelCase  =				None
										lowerCAmelCase  =				self.head

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





def 							lowercase					()     ->  None:


				'''simple docstring'''






				lowerCAmelCase  =				LinkedList()
				assert linked_list.is_empty() is True
				assert str(snake_case__ ) == ""

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

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

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





def 							lowercase					()     ->  None:


				'''simple docstring'''






				lowerCAmelCase  =				[
				    -9,
				    100,
				    Node(77_345_112 ),
				    """dlrow olleH""",
				    7,
				    5_555,
				    0,
				    -192.55_555,
				    """Hello, world!""",
				    77.9,
				    Node(10 ),
				    None,
				    None,
				    12.20,
				]
				lowerCAmelCase  =				LinkedList()

				for i in test_input:
								linked_list.insert_tail(snake_case__ )

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

				# Delete the tail
				lowerCAmelCase  =				linked_list.delete_tail()
				assert result == 12.2
				assert (
				    str(snake_case__ ) == "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  =				linked_list.delete_nth(10 )
				assert result is None
				assert (
				    str(snake_case__ ) == "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(snake_case__ )
				    == "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(snake_case__ )
				assert (
				    str(snake_case__ )
				    == "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(snake_case__ )
				    == "None->None->Node(10)->77.9->Hello, world!->-192.55555->0->5555->"
				    "7->dlrow olleH->Node(77345112)->100->Node(Hello again, world!)"
				)





def 							lowercase					()     ->  Union[str, Any]:


				'''simple docstring'''






				from doctest import testmod

				testmod()

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


if __name__ == "__main__":
		main()











"""simple docstring"""







from __future__ import annotations

import math
import random
from collections.abc import Collection
from typing import overload






class       SCREAMING_SNAKE_CASE__					:


						def __init__(							self				:			Dict						,						lowerCAmelCase				:			Collection[float] | None = None					):
										if components is None:
														lowerCAmelCase  =				[]
										lowerCAmelCase  =				list(lowerCAmelCase					)


						def __len__(							self				:			List[Any]					):
										return len(self.__components					)


						def __str__(							self				:			str					):
										return "(" + ",".join(map(lowerCAmelCase						,						self.__components					)					) + ")"


						def __add__(							self				:			Any						,						lowerCAmelCase				:			Vector					):
										lowerCAmelCase  =				len(self					)
										if size == len(lowerCAmelCase					):
														lowerCAmelCase  =				[self.__components[i] + other.component(lowerCAmelCase					) for i in range(lowerCAmelCase					)]
														return Vector(lowerCAmelCase					)
										else:
														raise Exception("""must have the same size"""					)


						def __sub__(							self				:			List[Any]						,						lowerCAmelCase				:			Vector					):
										lowerCAmelCase  =				len(self					)
										if size == len(lowerCAmelCase					):
														lowerCAmelCase  =				[self.__components[i] - other.component(lowerCAmelCase					) for i in range(lowerCAmelCase					)]
														return Vector(lowerCAmelCase					)
										else:  # error case
														raise Exception("""must have the same size"""					)


						@overload
						def __mul__(							self				:			Optional[int]						,						lowerCAmelCase				:			float					):
										...


						@overload
						def __mul__(							self				:			List[Any]						,						lowerCAmelCase				:			Vector					):
										...


						def __mul__(							self				:			Dict						,						lowerCAmelCase				:			float | Vector					):
										if isinstance(lowerCAmelCase						,						(float, int)					):
														lowerCAmelCase  =				[c * other for c in self.__components]
														return Vector(lowerCAmelCase					)
										elif isinstance(lowerCAmelCase						,						lowerCAmelCase					) and len(self					) == len(lowerCAmelCase					):
														lowerCAmelCase  =				len(self					)
														lowerCAmelCase  =				[self.__components[i] * other.component(lowerCAmelCase					) for i in range(lowerCAmelCase					)]
														return sum(lowerCAmelCase					)
										else:  # error case
														raise Exception("""invalid operand!"""					)


						def   __lowercase (							self				:			Tuple					):
										return Vector(self.__components					)


						def   __lowercase (							self				:			Dict						,						lowerCAmelCase				:			int					):
										if isinstance(lowerCAmelCase						,						lowerCAmelCase					) and -len(self.__components					) <= i < len(self.__components					):
														return self.__components[i]
										else:
														raise Exception("""index out of range"""					)


						def   __lowercase (							self				:			Any						,						lowerCAmelCase				:			int						,						lowerCAmelCase				:			float					):
										assert -len(self.__components					) <= pos < len(self.__components					)
										lowerCAmelCase  =				value


						def   __lowercase (							self				:			Optional[int]					):
										if len(self.__components					) == 0:
														raise Exception("""Vector is empty"""					)
										lowerCAmelCase  =				[c**2 for c in self.__components]
										return math.sqrt(sum(lowerCAmelCase					)					)




						def   __lowercase (							self				:			str						,						lowerCAmelCase				:			Vector						,						lowerCAmelCase				:			bool = False					):
										lowerCAmelCase  =				self * other
										lowerCAmelCase  =				self.euclidean_length() * other.euclidean_length()
										if deg:
														return math.degrees(math.acos(num / den					)					)
										else:
														return math.acos(num / den					)





def 							lowercase					(snake_case__   : int )     ->  Vector:


				'''simple docstring'''






				assert isinstance(snake_case__      ,       snake_case__ )
				return Vector([0] * dimension )





def 							lowercase					(snake_case__   : int      ,       snake_case__   : int )     ->  Vector:


				'''simple docstring'''






				assert isinstance(snake_case__      ,       snake_case__ ) and (isinstance(snake_case__      ,       snake_case__ ))
				lowerCAmelCase  =				[0] * dimension
				lowerCAmelCase  =				1
				return Vector(snake_case__ )





def 							lowercase					(snake_case__   : float      ,       snake_case__   : Vector      ,       snake_case__   : Vector )     ->  Vector:


				'''simple docstring'''






				assert (
				    isinstance(snake_case__      ,       snake_case__ )
				    and isinstance(snake_case__      ,       snake_case__ )
				    and (isinstance(snake_case__      ,       (int, float) ))
				)
				return x * scalar + y





def 							lowercase					(snake_case__   : int      ,       snake_case__   : int      ,       snake_case__   : int )     ->  Vector:


				'''simple docstring'''






				random.seed(snake_case__ )
				lowerCAmelCase  =				[random.randint(snake_case__      ,       snake_case__ ) for _ in range(snake_case__ )]
				return Vector(snake_case__ )






class       SCREAMING_SNAKE_CASE__					:


						def __init__(							self				:			Any						,						lowerCAmelCase				:			list[list[float]]						,						lowerCAmelCase				:			int						,						lowerCAmelCase				:			int					):
										lowerCAmelCase  =				matrix
										lowerCAmelCase  =				w
										lowerCAmelCase  =				h


						def __str__(							self				:			List[str]					):
										lowerCAmelCase  =				""""""
										for i in range(self.__height					):
														ans += "|"
														for j in range(self.__width					):
																		if j < self.__width - 1:
																						ans += str(self.__matrix[i][j]					) + ","
																		else:
																						ans += str(self.__matrix[i][j]					) + "|\n"
										return ans


						def __add__(							self				:			Optional[Any]						,						lowerCAmelCase				:			Matrix					):
										if self.__width == other.width() and self.__height == other.height():
														lowerCAmelCase  =				[]
														for i in range(self.__height					):
																		lowerCAmelCase  =				[
																		    self.__matrix[i][j] + other.component(lowerCAmelCase						,						lowerCAmelCase					)
																		    for j in range(self.__width					)
																		]
																		matrix.append(lowerCAmelCase					)
														return Matrix(lowerCAmelCase						,						self.__width						,						self.__height					)
										else:
														raise Exception("""matrix must have the same dimension!"""					)


						def __sub__(							self				:			Union[str, Any]						,						lowerCAmelCase				:			Matrix					):
										if self.__width == other.width() and self.__height == other.height():
														lowerCAmelCase  =				[]
														for i in range(self.__height					):
																		lowerCAmelCase  =				[
																		    self.__matrix[i][j] - other.component(lowerCAmelCase						,						lowerCAmelCase					)
																		    for j in range(self.__width					)
																		]
																		matrix.append(lowerCAmelCase					)
														return Matrix(lowerCAmelCase						,						self.__width						,						self.__height					)
										else:
														raise Exception("""matrices must have the same dimension!"""					)


						@overload
						def __mul__(							self				:			Any						,						lowerCAmelCase				:			float					):
										...


						@overload
						def __mul__(							self				:			Optional[int]						,						lowerCAmelCase				:			Vector					):
										...


						def __mul__(							self				:			Dict						,						lowerCAmelCase				:			float | Vector					):
										if isinstance(lowerCAmelCase						,						lowerCAmelCase					):  # matrix-vector
														if len(lowerCAmelCase					) == self.__width:
																		lowerCAmelCase  =				zero_vector(self.__height					)
																		for i in range(self.__height					):
																						lowerCAmelCase  =				[
																						    self.__matrix[i][j] * other.component(lowerCAmelCase					)
																						    for j in range(self.__width					)
																						]
																						ans.change_component(lowerCAmelCase						,						sum(lowerCAmelCase					)					)
																		return ans
														else:
																		raise Exception(
																		    """vector must have the same size as the """
																		    """number of columns of the matrix!"""					)
										elif isinstance(lowerCAmelCase						,						(int, float)					):  # matrix-scalar
														lowerCAmelCase  =				[
														    [self.__matrix[i][j] * other for j in range(self.__width					)]
														    for i in range(self.__height					)
														]
														return Matrix(lowerCAmelCase						,						self.__width						,						self.__height					)
										return None


						def   __lowercase (							self				:			Any					):
										return self.__height


						def   __lowercase (							self				:			int					):
										return self.__width


						def   __lowercase (							self				:			Optional[Any]						,						lowerCAmelCase				:			int						,						lowerCAmelCase				:			int					):
										if 0 <= x < self.__height and 0 <= y < self.__width:
														return self.__matrix[x][y]
										else:
														raise Exception("""change_component: indices out of bounds"""					)


						def   __lowercase (							self				:			int						,						lowerCAmelCase				:			int						,						lowerCAmelCase				:			int						,						lowerCAmelCase				:			float					):
										if 0 <= x < self.__height and 0 <= y < self.__width:
														lowerCAmelCase  =				value
										else:
														raise Exception("""change_component: indices out of bounds"""					)


						def   __lowercase (							self				:			int						,						lowerCAmelCase				:			int						,						lowerCAmelCase				:			int					):
										if self.__height != self.__width:
														raise Exception("""Matrix is not square"""					)
										lowerCAmelCase  =				self.__matrix[:x] + self.__matrix[x + 1 :]
										for i in range(len(lowerCAmelCase					)					):
														lowerCAmelCase  =				minor[i][:y] + minor[i][y + 1 :]
										return Matrix(lowerCAmelCase						,						self.__width - 1						,						self.__height - 1					).determinant()


						def   __lowercase (							self				:			Optional[Any]						,						lowerCAmelCase				:			int						,						lowerCAmelCase				:			int					):
										if self.__height != self.__width:
														raise Exception("""Matrix is not square"""					)
										if 0 <= x < self.__height and 0 <= y < self.__width:
														return (-1) ** (x + y) * self.minor(lowerCAmelCase						,						lowerCAmelCase					)
										else:
														raise Exception("""Indices out of bounds"""					)




						def   __lowercase (							self				:			List[Any]					):
										if self.__height != self.__width:
														raise Exception("""Matrix is not square"""					)
										if self.__height < 1:
														raise Exception("""Matrix has no element"""					)
										elif self.__height == 1:
														return self.__matrix[0][0]
										elif self.__height == 2:
														return (
														    self.__matrix[0][0] * self.__matrix[1][1]
														    - self.__matrix[0][1] * self.__matrix[1][0]
														)
										else:
														lowerCAmelCase  =				[
														    self.__matrix[0][y] * self.cofactor(0						,						lowerCAmelCase					) for y in range(self.__width					)
														]
														return sum(lowerCAmelCase					)





def 							lowercase					(snake_case__   : int )     ->  Matrix:


				'''simple docstring'''






				lowerCAmelCase  =				[[0] * n for _ in range(snake_case__ )]
				return Matrix(snake_case__      ,       snake_case__      ,       snake_case__ )






def 							lowercase					(snake_case__   : int      ,       snake_case__   : int      ,       snake_case__   : int      ,       snake_case__   : int )     ->  Matrix:


				'''simple docstring'''






				random.seed(snake_case__ )
				lowerCAmelCase  =				[
				    [random.randint(snake_case__      ,       snake_case__ ) for _ in range(snake_case__ )] for _ in range(snake_case__ )
				]
				return Matrix(snake_case__      ,       snake_case__      ,       snake_case__ )





