



import timeit







class      __lowerCAmelCase       :



			def __init__(		self  :    List[str]					,						A  :    Any)  ->       str:



						"""simple docstring"""






						if isinstance(A					,						A):  # Initializes a matrix identical to the one provided.
									_UpperCAmelCase									=  arg
									_UpperCAmelCase									=  len(A)
						else:  # Initializes a square matrix of the given size and set values to zero.
									_UpperCAmelCase									=  arg
									_UpperCAmelCase									=  [[0 for _ in range(self.n)] for _ in range(self.n)]



			def __mul__(		self  :    Union[str, Any]					,						A  :    Optional[Any])  ->       int:



						"""simple docstring"""






						_UpperCAmelCase									=  Matrix(self.n)
						for i in range(self.n):
									for j in range(self.n):
												for k in range(self.n):
															matrix.t[i][j] += self.t[i][k] * b.t[k][j]
						return matrix





def 				A      (	_UpperCAmelCase							:  List[Any]				,  _UpperCAmelCase							:  str       )							->					List[Any]:







			'''simple docstring'''
			_UpperCAmelCase									=  Matrix([[1, 0], [0, 1]]       )
			while b > 0:
						if b & 1:
									matrix *= a
						a *= a
						b >>= 1
			return matrix





def 				A      (	_UpperCAmelCase							:  Tuple				,  _UpperCAmelCase							:  Any				,  _UpperCAmelCase							:  Tuple       )							->					Any:







			'''simple docstring'''
			# Trivial Cases
			if n == 1:
						return fa
			elif n == 2:
						return fa
			_UpperCAmelCase									=  Matrix([[1, 1], [1, 0]]       )
			_UpperCAmelCase									=  modular_exponentiation(_UpperCAmelCase				,  n - 2       )
			return fa * matrix.t[0][0] + fa * matrix.t[0][1]





def 				A      (	_UpperCAmelCase							:  List[Any]				,  _UpperCAmelCase							:  List[Any]				,  _UpperCAmelCase							:  Optional[Any]       )							->					Tuple:







			'''simple docstring'''
			# Trivial Cases
			if n == 1:
						return fa
			elif n == 2:
						return fa

			_UpperCAmelCase									=  fa
			_UpperCAmelCase									=  fa
			n -= 2

			while n > 0:
						_UpperCAmelCase			,	_UpperCAmelCase									=  fn_a + fn_a, fn_a
						n -= 1

			return fn_a





def 				A      (	)							->					Dict:







			'''simple docstring'''
			_UpperCAmelCase									=  '\nfrom random import randint\nfrom __main__ import fibonacci_with_matrix_exponentiation\n'
			_UpperCAmelCase									=  'fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)'
			_UpperCAmelCase									=  timeit.timeit(setup=_UpperCAmelCase				,  stmt=_UpperCAmelCase				,  number=100       )
			print('With matrix exponentiation the average execution time is '				,  exec_time / 100       )
			return exec_time





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







			'''simple docstring'''
			_UpperCAmelCase									=  '\nfrom random import randint\nfrom __main__ import simple_fibonacci\n'
			_UpperCAmelCase									=  'simple_fibonacci(randint(1,70000), 1, 1)'
			_UpperCAmelCase									=  timeit.timeit(setup=_UpperCAmelCase				,  stmt=_UpperCAmelCase				,  number=100       )
			print(
			    'Without matrix exponentiation the average execution time is '				,  exec_time / 100       )
			return exec_time





def 				A      (	)							->					Optional[int]:







			'''simple docstring'''
			matrix_exponentiation_time()
			simple_fibonacci_time()


if __name__ == "__main__":
							main()





def 				A      (	_UpperCAmelCase							:  List[Any]       )							->					List[Any]:







			'''simple docstring'''
			_UpperCAmelCase									=  len(_UpperCAmelCase       )
			for _ in range(
			    0				,  int(((no_of_elements - 1) / 2) + 1       )       ):  # we don't need to traverse to end of list as
						for j in range(0				,  no_of_elements - 1       ):
									if (
									    lst[j + 1] < lst[j]
									):  # applying bubble sort algorithm from left to right (or forwards)
												_UpperCAmelCase									=  lst[j + 1]
												_UpperCAmelCase									=  lst[j]
												_UpperCAmelCase									=  temp
									if (
									    lst[no_of_elements - 1 - j] < lst[no_of_elements - 2 - j]
									):  # applying bubble sort algorithm from right to left (or backwards)
												_UpperCAmelCase									=  lst[no_of_elements - 1 - j]
												_UpperCAmelCase									=  lst[no_of_elements - 2 - j]
												_UpperCAmelCase									=  temp
			return lst


if __name__ == "__main__":
							print("enter the list to be sorted")
							UpperCAmelCase__  =			[int(x) for x in input().split()]  # inputing elements of the list in one line
							UpperCAmelCase__  =			double_sort(lst)
							print("the sorted list is")
							print(sorted_lst)
