
from typing import Any







class        lowerCAmelCase__      :

						def __init__(			self       ,							a				)					->      Optional[int]:


								'''simple docstring'''

								_UpperCamelCase						    =	data
								_UpperCamelCase						    =	None







						def __repr__(			self				)					->      Dict:


								'''simple docstring'''

								return F'Node({self.data})'







class        lowerCAmelCase__      :

						def __init__(			self				)					->      Optional[Any]:


								'''simple docstring'''

								_UpperCamelCase						    =	None

						def __iter__(			self				)					->      List[str]:


								'''simple docstring'''

								_UpperCamelCase						    =	self.head
								while node:
										yield node.data
										_UpperCamelCase						    =	node.next

						def __len__(			self				)					->      Tuple:


								'''simple docstring'''

								return sum(1 for _ in self				)

						def __repr__(			self				)					->      List[Any]:


								'''simple docstring'''

								return "->".join([str(lowerCamelCase_				) for item in self]				)

						def __getitem__(			self       ,							a				)					->      List[Any]:


								'''simple docstring'''

								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       ,							a       ,							a				)					->      Optional[int]:


								'''simple docstring'''

								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  A_				(			self       ,							a				)					->      Optional[int]:


								'''simple docstring'''

								self.insert_nth(len(self				)       ,							lowerCamelCase_				)

						def  A_				(			self       ,							a				)					->      Optional[Any]:


								'''simple docstring'''

								self.insert_nth(0       ,							lowerCamelCase_				)

						def  A_				(			self       ,							a       ,							a				)					->      Optional[Any]:


								'''simple docstring'''

								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  A_				(			self				)					->      Union[str, Any]:  # print every node data


								'''simple docstring'''

								print(self				)

						def  A_				(			self				)					->      Optional[int]:


								'''simple docstring'''

								return self.delete_nth(0				)

						def  A_				(			self				)					->      List[str]:  # delete from tail


								'''simple docstring'''

								return self.delete_nth(len(self				) - 1				)

						def  A_				(			self       ,							a = 0				)					->      Optional[int]:


								'''simple docstring'''

								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  A_				(			self				)					->      int:


								'''simple docstring'''

								return self.head is None







						def  A_				(			self				)					->      List[Any]:


								'''simple docstring'''

								_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 							__A()		->				Dict:

		"""simple docstring"""






		_UpperCamelCase						    =	LinkedList()
		assert linked_list.is_empty() is True
		assert str(lowerCamelCase_ ) == ""

		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(1_0 ):
				assert len(lowerCamelCase_ ) == i
				linked_list.insert_nth(lowerCamelCase_						,  i + 1 )
		assert str(lowerCamelCase_ ) == "->".join(str(lowerCamelCase_ ) for i in range(1						,  1_1 ) )

		linked_list.insert_head(0 )
		linked_list.insert_tail(1_1 )
		assert str(lowerCamelCase_ ) == "->".join(str(lowerCamelCase_ ) for i in range(0						,  1_2 ) )

		assert linked_list.delete_head() == 0
		assert linked_list.delete_nth(9 ) == 1_0
		assert linked_list.delete_tail() == 1_1
		assert len(lowerCamelCase_ ) == 9
		assert str(lowerCamelCase_ ) == "->".join(str(lowerCamelCase_ ) for i in range(1						,  1_0 ) )

		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(lowerCamelCase_ ) == "->".join(str(lowerCamelCase_ ) for i in range(-8						,  1 ) )


def 							__A()		->				Dict:

		"""simple docstring"""






		_UpperCamelCase						    =	[
		    -9,
		    1_0_0,
		    Node(7_7_3_4_5_1_1_2 ),
		    """dlrow olleH""",
		    7,
		    5_5_5_5,
		    0,
		    -192.55555,
		    """Hello, world!""",
		    77.9,
		    Node(1_0 ),
		    None,
		    None,
		    12.20,
		]
		_UpperCamelCase						    =	LinkedList()

		for i in test_input:
				linked_list.insert_tail(lowerCamelCase_ )

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


def 							__A()		->				Any:

		"""simple docstring"""






		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(lowerCamelCase_ )
		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(lowerCamelCase_ )
		print(F'length of linked_list is : {len(lowerCamelCase_ )}' )


if __name__ == "__main__":
						main()





def 							__A(lowerCAmelCase )		->				list[list[int]]:

		"""simple docstring"""






		_UpperCamelCase						    =	[]
		if len(lowerCAmelCase ) == 1:
				return [nums.copy()]
		for _ in range(len(lowerCAmelCase ) ):
				_UpperCamelCase						    =	nums.pop(0 )
				_UpperCamelCase						    =	permute(lowerCAmelCase )
				for perm in permutations:
						perm.append(lowerCAmelCase )
				result.extend(lowerCAmelCase )
				nums.append(lowerCAmelCase )
		return result


def 							__A(lowerCAmelCase )		->				Optional[int]:

		"""simple docstring"""






		def backtrack(lowerCAmelCase ):
				if start == len(lowerCAmelCase ) - 1:
						output.append(nums[:] )
				else:
						for i in range(lowerCAmelCase						,  len(lowerCAmelCase ) ):
								_UpperCamelCase    ,	_UpperCamelCase						    =	nums[i], nums[start]
								backtrack(start + 1 )
								_UpperCamelCase    ,	_UpperCamelCase						    =	nums[i], nums[start]  # backtrack

		_UpperCamelCase						    =	[]
		backtrack(0 )
		return output


if __name__ == "__main__":
		import doctest

		# use res to print the data in permute2 function
		lowerCamelCase__	=							permutea([1, 2, 3])
		print(res)
		doctest.testmod()



