





class SCREAMING_SNAKE_CASE_ :





					"""simple docstring"""


					def __init__( self	,  _lowerCAmelCase	,  _lowerCAmelCase=None	,  _lowerCAmelCase=None	):
										lowerCamelCase__       =       data
										lowerCamelCase__       =       previous
										lowerCamelCase__       =       next_node





					def __str__( self	):
										return F"{self.data}"





					def 					__magic_name__ ( self	):
										return self.data





					def 					__magic_name__ ( self	):
										return self.next






					def 					__magic_name__ ( self	):
										return self.previous

class SCREAMING_SNAKE_CASE_ :





					"""simple docstring"""


					def __init__( self	,  _lowerCAmelCase	):
										lowerCamelCase__       =       head





					def __iter__( self	):
										return self






					def 					__magic_name__ ( self	):
										if not self.current:
															raise StopIteration
										else:
															lowerCamelCase__       =       self.current.get_data()
															lowerCamelCase__       =       self.current.get_next()
															return value

class SCREAMING_SNAKE_CASE_ :





					"""simple docstring"""


					def __init__( self	):
										lowerCamelCase__       =       None  # First node in list
										lowerCamelCase__       =       None  # Last node in list





					def __str__( self	):
										lowerCamelCase__       =       self.head
										lowerCamelCase__       =       []
										while current is not None:
															nodes.append(current.get_data()	)
															lowerCamelCase__       =       current.get_next()
										return " ".join(str(_lowerCAmelCase	) for node in nodes	)





					def __contains__( self	,  _lowerCAmelCase	):
										lowerCamelCase__       =       self.head
										while current:
															if current.get_data() == value:
																				return True
															lowerCamelCase__       =       current.get_next()
										return False





					def __iter__( self	):
										return LinkedListIterator(self.head	)





					def 					__magic_name__ ( self	):
										if self.head:
															return self.head.get_data()
										return None





					def 					__magic_name__ ( self	):
										if self.tail:
															return self.tail.get_data()
										return None





					def 					__magic_name__ ( self	,  _lowerCAmelCase	):
										if self.head is None:
															lowerCamelCase__       =       node
															lowerCamelCase__       =       node
										else:
															self.insert_before_node(self.head	,  _lowerCAmelCase	)





					def 					__magic_name__ ( self	,  _lowerCAmelCase	):
										if self.head is None:
															self.set_head(_lowerCAmelCase	)
										else:
															self.insert_after_node(self.tail	,  _lowerCAmelCase	)





					def 					__magic_name__ ( self	,  _lowerCAmelCase	):
										lowerCamelCase__       =       Node(_lowerCAmelCase	)
										if self.head is None:
															self.set_head(_lowerCAmelCase	)
										else:
															self.set_tail(_lowerCAmelCase	)





					def 					__magic_name__ ( self	,  _lowerCAmelCase	,  _lowerCAmelCase	):
										lowerCamelCase__       =       node
										lowerCamelCase__       =       node.previous

										if node.get_previous() is None:
															lowerCamelCase__       =       node_to_insert
										else:
															lowerCamelCase__       =       node_to_insert

										lowerCamelCase__       =       node_to_insert





					def 					__magic_name__ ( self	,  _lowerCAmelCase	,  _lowerCAmelCase	):
										lowerCamelCase__       =       node
										lowerCamelCase__       =       node.next

										if node.get_next() is None:
															lowerCamelCase__       =       node_to_insert
										else:
															lowerCamelCase__       =       node_to_insert

										lowerCamelCase__       =       node_to_insert





					def 					__magic_name__ ( self	,  _lowerCAmelCase	,  _lowerCAmelCase	):
										lowerCamelCase__       =       1
										lowerCamelCase__       =       Node(_lowerCAmelCase	)
										lowerCamelCase__       =       self.head
										while node:
															if current_position == position:
																				self.insert_before_node(_lowerCAmelCase	,  _lowerCAmelCase	)
																				return
															current_position += 1
															lowerCamelCase__       =       node.next
										self.insert_after_node(self.tail	,  _lowerCAmelCase	)





					def 					__magic_name__ ( self	,  _lowerCAmelCase	):
										lowerCamelCase__       =       self.head
										while node:
															if node.get_data() == item:
																				return node
															lowerCamelCase__       =       node.get_next()
										raise Exception("Node not found"	)





					def 					__magic_name__ ( self	,  _lowerCAmelCase	):
										if (node := self.get_node(_lowerCAmelCase	)) is not None:
															if node == self.head:
																				lowerCamelCase__       =       self.head.get_next()

															if node == self.tail:
																				lowerCamelCase__       =       self.tail.get_previous()

															self.remove_node_pointers(_lowerCAmelCase	)





					@staticmethod
					def 					__magic_name__ ( _lowerCAmelCase	):
										if node.get_next():
															lowerCamelCase__       =       node.previous

										if node.get_previous():
															lowerCamelCase__       =       node.next

										lowerCamelCase__       =       None
										lowerCamelCase__       =       None






					def 					__magic_name__ ( self	):
										return self.head is None





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




if __name__ == "__main__":
						import doctest

						doctest.testmod()








def    __UpperCamelCase      (    a,     a) ->Optional[int]:
					lowerCamelCase__       =       [1]
					for i in range(2,     a):
										factorials.append(factorials[-1] * i)
					assert 0 <= k < factorials[-1] * n, "k out of bounds"

					lowerCamelCase__       =       []
					lowerCamelCase__       =       list(range(a))

					# Find permutation
					while factorials:
										lowerCamelCase__       =       factorials.pop()
										lowerCamelCase__    ,		lowerCamelCase__       =       divmod(a,     a)
										permutation.append(elements[number])
										elements.remove(elements[number])
					permutation.append(elements[0])

					return permutation


if __name__ == "__main__":
						import doctest

						doctest.testmod()

