


from __future__ import annotations

from collections.abc import Iterable, Iterator
from dataclasses import dataclass

lowerCAmelCase__			:      Union[str, Any]								=(3, 9, -11, 0, 7, 5, 1, -1)
lowerCAmelCase__			:      Optional[Any]								=(4, 6, 2, 0, 8, 10, 3, -2)







@dataclass
class 	__lowercase    :





							"""simple docstring"""







							_UpperCAmelCase      =						42
							_UpperCAmelCase      =						42







class 	__lowercase    :





							"""simple docstring"""







							def __init__(      self			,						lowerCAmelCase__       ):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:     Any					=					None
										for i in sorted(lowerCAmelCase__			,						reverse=lowerCAmelCase__       ):
													SCREAMING_SNAKE_CASE_		:     Dict					=					Node(lowerCAmelCase__			,						self.head       )






							def __iter__(      self       ):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:     str					=					self.head
										while node:
													yield node.data
													SCREAMING_SNAKE_CASE_		:     Optional[Any]					=					node.next_node






							def __len__(      self       ):





										"""simple docstring"""




										return sum(1 for _ in self       )






							def __str__(      self       ):





										"""simple docstring"""




										return " -> ".join([str(lowerCAmelCase__       ) for node in self]       )







def 						a__			(				A__,      A__				):
			return SortedLinkedList(list(_A				) + list(_A				)				)


if __name__ == "__main__":
				import doctest

				doctest.testmod()
				lowerCAmelCase__			:      List[str]								=SortedLinkedList
				print(merge_lists(SSL(test_data_odd), SSL(test_data_even)))









__UpperCamelCase     		=							2_5_6
# Modulus to hash a string
__UpperCamelCase     		=							1_0_0_0_0_0_3
def 							UpperCamelCase_(					_A :str					,  _A :str	)->		bool:
			UpperCamelCase__       =							len(_A	)
			UpperCamelCase__       =							len(_A	)
			if p_len > t_len:
						return False

			UpperCamelCase__       =							0
			UpperCamelCase__       =							0
			UpperCamelCase__       =							1

			# Calculating the hash of pattern and substring of text
			for i in range(_A	):
						UpperCamelCase__       =							(ord(pattern[i]	) + p_hash * alphabet_size) % modulus
						UpperCamelCase__       =							(ord(text[i]	) + text_hash * alphabet_size) % modulus
						if i == p_len - 1:
									continue
						UpperCamelCase__       =							(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
						UpperCamelCase__       =							(
						    (text_hash - ord(text[i]	) * modulus_power) * alphabet_size
						    + ord(text[i + p_len]	)
						) % modulus
			return False
def 							UpperCamelCase_(					)->		None:
			UpperCamelCase__       =							"abc1abc12"
			UpperCamelCase__       =							"alskfjaldsabc1abc1abc12k23adsfabcabc"
			UpperCamelCase__       =							"alskfjaldsk23adsfabcabc"
			assert rabin_karp(_A					,  _A	) and not rabin_karp(_A					,  _A	)

			# Test 2)
			UpperCamelCase__       =							"ABABX"
			UpperCamelCase__       =							"ABABZABABYABABX"
			assert rabin_karp(_A					,  _A	)

			# Test 3)
			UpperCamelCase__       =							"AAAB"
			UpperCamelCase__       =							"ABAAAAAB"
			assert rabin_karp(_A					,  _A	)

			# Test 4)
			UpperCamelCase__       =							"abcdabcy"
			UpperCamelCase__       =							"abcxabcdabxabcdabcdabcy"
			assert rabin_karp(_A					,  _A	)

			# Test 5)
			UpperCamelCase__       =							"Lü"
			UpperCamelCase__       =							"Lüsai"
			assert rabin_karp(_A					,  _A	)
			UpperCamelCase__       =							"Lue"
			assert not rabin_karp(_A					,  _A	)
			print("Success."	)


if __name__ == "__main__":
						test_rabin_karp()


