"""simple docstring"""







import re

from flax.core.frozen_dict import freeze
from flax.traverse_util import flatten_dict, unflatten_dict
from jax.experimental import PartitionSpec as P


# Sentinels
SCREAMING_SNAKE_CASE									=						object()

# For specifying empty leaf dict `{}`
SCREAMING_SNAKE_CASE									=						object()


def      __lowerCAmelCase(		__UpperCAmelCase     ,__UpperCAmelCase			):






	"""simple docstring"""





	_lowercase :    Optional[int]							=							tuple((re.compile(x + '$'			) for x in qs)			)
	for i in range(len(__UpperCamelCase			) - len(__UpperCamelCase			) + 1			):
		_lowercase :    Tuple							=							[x.match(__UpperCamelCase			) for x, y in zip(__UpperCamelCase     ,ks[i:]			)]
		if matches and all(__UpperCamelCase			):
			return True
	return False


def      __lowerCAmelCase(		__UpperCAmelCase			):






	"""simple docstring"""





	def replace(__UpperCAmelCase     ,__UpperCAmelCase			):
		for rule, replacement in rules:
			if _match(__UpperCamelCase     ,__UpperCamelCase			):
				return replacement
		return val

	return replace


def      __lowerCAmelCase(		):






	"""simple docstring"""





	return [
	    # embeddings
	    (("transformer", "wpe", "embedding"), P('mp'     ,__UpperCamelCase			)),
	    (("transformer", "wte", "embedding"), P('mp'     ,__UpperCamelCase			)),
	    # atention
	    (("attention", "(q_proj|k_proj|v_proj)", "kernel"), P(__UpperCamelCase     ,'mp'			)),
	    (("attention", "out_proj", "kernel"), P('mp'     ,__UpperCamelCase			)),
	    (("attention", "out_proj", "bias"), None),
	    # mlp
	    (("mlp", "c_fc", "kernel"), P(__UpperCamelCase     ,'mp'			)),
	    (("mlp", "c_fc", "bias"), P('mp'			)),
	    (("mlp", "c_proj", "kernel"), P('mp'     ,__UpperCamelCase			)),
	    (("mlp", "c_proj", "bias"), None),
	    # layer norms
	    ((r"ln_\d+", "bias"), None),
	    ((r"\d+", r"ln_\d+", "scale"), None),
	    (("ln_f", "bias"), None),
	    (("ln_f", "scale"), None),
	]







def      __lowerCAmelCase(		__UpperCAmelCase			):






	"""simple docstring"""





	_lowercase :    Optional[Any]							=							_get_partition_rules()
	_lowercase :    Dict							=							_replacement_rules(__UpperCamelCase			)
	_lowercase :    Optional[int]							=							{k: _unmatched for k in flatten_dict(__UpperCamelCase			)}
	_lowercase :    Tuple							=							{k: replace(__UpperCamelCase     ,__UpperCamelCase			) for k, v in initd.items()}
	assert _unmatched not in result.values(), "Incomplete partition spec."
	return freeze(unflatten_dict(__UpperCamelCase			)			)







"""simple docstring"""







def      __lowerCAmelCase(		__UpperCAmelCase			):






	"""simple docstring"""





	stooge(__UpperCAmelCase     ,0     ,len(__UpperCAmelCase			) - 1			)
	return arr


def      __lowerCAmelCase(		__UpperCAmelCase     ,__UpperCAmelCase     ,__UpperCAmelCase			):






	"""simple docstring"""





	if i >= h:
		return

	# If first element is smaller than the last then swap them
	if arr[i] > arr[h]:
		_lowercase				,      _lowercase :    List[str]							=							arr[h], arr[i]

	# If there are more than 2 elements in the array
	if h - i + 1 > 2:
		_lowercase :    Optional[int]							=							(int)((h - i + 1) / 3			)

		# Recursively sort first 2/3 elements
		stooge(__UpperCAmelCase     ,__UpperCAmelCase     ,(h - t)			)

		# Recursively sort last 2/3 elements
		stooge(__UpperCAmelCase     ,i + t     ,(__UpperCAmelCase)			)

		# Recursively sort first 2/3 elements
		stooge(__UpperCAmelCase     ,__UpperCAmelCase     ,(h - t)			)


if __name__ == "__main__":
						SCREAMING_SNAKE_CASE									=						input('Enter numbers separated by a comma:\n').strip()
						SCREAMING_SNAKE_CASE									=						[int(item) for item in user_input.split(',')]
						print(stooge_sort(unsorted))



