





import operator






def 					SCREAMING_SNAKE_CASE__				(							UpperCamelCase__:				list       , UpperCamelCase__:				bool = False       , UpperCamelCase__:				list | None = None     ):
		SCREAMING_SNAKE_CASE__								=   operator.lt if reverse else operator.gt
		SCREAMING_SNAKE_CASE__								=   solution or []

		if not arr:
				return solution

		SCREAMING_SNAKE_CASE__								=   [arr.pop(0     )]
		for i, item in enumerate(UpperCamelCase__     ):
				if _operator(UpperCamelCase__       , sublist[-1]     ):
						sublist.append(UpperCamelCase__     )
						arr.pop(UpperCamelCase__     )

    #  merging sublist into solution list
		if not solution:
				solution.extend(UpperCamelCase__     )
		else:
				while sublist:
						SCREAMING_SNAKE_CASE__								=   sublist.pop(0     )
						for i, xx in enumerate(UpperCamelCase__     ):
								if not _operator(UpperCamelCase__       , UpperCamelCase__     ):
										solution.insert(UpperCamelCase__       , UpperCamelCase__     )
										break
						else:
								solution.append(UpperCamelCase__     )

		strand_sort(UpperCamelCase__       , UpperCamelCase__       , UpperCamelCase__     )
		return solution


if __name__ == "__main__":
	assert strand_sort([4, 3, 5, 1, 2]) == [1, 2, 3, 4, 5]
	assert strand_sort([4, 3, 5, 1, 2], reverse=True) == [5, 4, 3, 2, 1]




_lowerCamelCase    :		Optional[Any]		      =    256
# Modulus to hash a string
_lowerCamelCase    :		Optional[Any]		      =    1_000_003

def        __a			(   __lowerCAmelCase      ,	__lowerCAmelCase   )     ->     bool:
					SCREAMING_SNAKE_CASE							:     Tuple						=				len(__lowerCAmelCase   )
					SCREAMING_SNAKE_CASE							:     Tuple						=				len(__lowerCAmelCase   )
					if p_len > t_len:
										return False

					SCREAMING_SNAKE_CASE							:     Dict						=				0
					SCREAMING_SNAKE_CASE							:     Tuple						=				0
					SCREAMING_SNAKE_CASE							:     Optional[Any]						=				1

					# Calculating the hash of pattern and substring of text
					for i in range(__lowerCAmelCase   ):
										SCREAMING_SNAKE_CASE							:     Tuple						=				(ord(pattern[i]   ) + p_hash * alphabet_size) % modulus
										SCREAMING_SNAKE_CASE							:     Union[str, Any]						=				(ord(text[i]   ) + text_hash * alphabet_size) % modulus
										if i == p_len - 1:
															continue
										SCREAMING_SNAKE_CASE							:     Optional[Any]						=				(modulus_power * alphabet_size) % modulus

					for i in range(0      ,	t_len - p_len + 1   ):
										if text_hash == p_hash and text[i : i + p_len] == pattern:
															return True
										if i == t_len - p_len:
															continue
										# Calculate the https://en.wikipedia.org/wiki/Rolling_hash
										SCREAMING_SNAKE_CASE							:     int						=				(
										    (text_hash - ord(text[i]   ) * modulus_power) * alphabet_size
										    + ord(text[i + p_len]   )
										) % modulus
					return False

def        __a			(   )     ->     None:
					SCREAMING_SNAKE_CASE							:     Any						=				'abc1abc12'
					SCREAMING_SNAKE_CASE							:     str						=				'alskfjaldsabc1abc1abc12k23adsfabcabc'
					SCREAMING_SNAKE_CASE							:     List[str]						=				'alskfjaldsk23adsfabcabc'
					assert rabin_karp(__lowerCAmelCase      ,	__lowerCAmelCase   ) and not rabin_karp(__lowerCAmelCase      ,	__lowerCAmelCase   )

					# Test 2)
					SCREAMING_SNAKE_CASE							:     List[str]						=				'ABABX'
					SCREAMING_SNAKE_CASE							:     int						=				'ABABZABABYABABX'
					assert rabin_karp(__lowerCAmelCase      ,	__lowerCAmelCase   )

					# Test 3)
					SCREAMING_SNAKE_CASE							:     int						=				'AAAB'
					SCREAMING_SNAKE_CASE							:     Tuple						=				'ABAAAAAB'
					assert rabin_karp(__lowerCAmelCase      ,	__lowerCAmelCase   )

					# Test 4)
					SCREAMING_SNAKE_CASE							:     Tuple						=				'abcdabcy'
					SCREAMING_SNAKE_CASE							:     Optional[Any]						=				'abcxabcdabxabcdabcdabcy'
					assert rabin_karp(__lowerCAmelCase      ,	__lowerCAmelCase   )

					# Test 5)
					SCREAMING_SNAKE_CASE							:     List[Any]						=				'Lü'
					SCREAMING_SNAKE_CASE							:     Optional[Any]						=				'Lüsai'
					assert rabin_karp(__lowerCAmelCase      ,	__lowerCAmelCase   )
					SCREAMING_SNAKE_CASE							:     Union[str, Any]						=				'Lue'
					assert not rabin_karp(__lowerCAmelCase      ,	__lowerCAmelCase   )
					print('Success.'   )


if __name__ == "__main__":
			test_rabin_karp()