





"""simple docstring"""




def 	a_    (							_lowercase	,						_lowercase       ):






						"""simple docstring"""




						_UpperCamelCase      : int         =   [1]
						for i in range(2	,						_lowercase       ):
												factorials.append(factorials[-1] * i       )
						assert 0 <= k < factorials[-1] * n, "k out of bounds"

						_UpperCamelCase      : str         =   []
						_UpperCamelCase      : List[Any]         =   list(range(_lowercase       )       )

						# Find permutation
						while factorials:
												_UpperCamelCase      : Optional[Any]         =   factorials.pop()
												_UpperCamelCase      : Dict         =   divmod(_lowercase	,						_lowercase       )
												permutation.append(elements[number]       )
												elements.remove(elements[number]       )
						permutation.append(elements[0]       )

						return permutation


if __name__ == "__main__":
						import doctest

						doctest.testmod()










"""simple docstring"""




from __future__ import annotations

from random import choice





def 	a_    (							_lowercase       ):
						return choice(_lowercase       )





def 	a_    (							_lowercase	,						_lowercase       ):
						_UpperCamelCase      : Optional[int]         =   random_pivot(_lowercase       )

						# partition based on pivot
						# linear time
						_UpperCamelCase      : Union[str, Any]         =   [e for e in lst if e < pivot]
						_UpperCamelCase      : int         =   [e for e in lst if e > pivot]

						# if we get lucky, pivot might be the element we want.
						# we can easily see this:
						# small (elements smaller than k)
						# + pivot (kth element)
						# + big (elements larger than k)
						if len(_lowercase       ) == k - 1:
												return pivot
						# pivot is in elements bigger than k
						elif len(_lowercase       ) < k - 1:
												return kth_number(_lowercase	,						k - len(_lowercase       ) - 1       )
						# pivot is in elements smaller than k
						else:
												return kth_number(_lowercase	,						_lowercase       )


if __name__ == "__main__":
						import doctest

						doctest.testmod()



