from __future__ import annotations

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

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





@dataclass
class 					lowercase__						:
						UpperCamelCase_     =		42
						UpperCamelCase_     =		42






class 					lowercase__						:


						def __init__(       self	:				Optional[Any]    ,		UpperCamelCase__	:				Iterable[int]						):





												'''simple docstring'''





												SCREAMING_SNAKE_CASE							:    Dict							=							None
												for i in sorted(__A    ,		reverse=__A						):
																		SCREAMING_SNAKE_CASE							:    Optional[Any]							=							Node(__A    ,		self.head						)


						def __iter__(       self	:				Any						):





												'''simple docstring'''





												SCREAMING_SNAKE_CASE							:    Tuple							=							self.head
												while node:
																		yield node.data
																		SCREAMING_SNAKE_CASE							:    Dict							=							node.next_node


						def __len__(       self	:				Optional[int]						):





												'''simple docstring'''





												return sum(1 for _ in self						)



						def __str__(       self	:				List[Any]						):





												'''simple docstring'''





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






def       A	(    _lowercase		,  _lowercase						):
						return SortedLinkedList(list(__lowercase						) + list(__lowercase						)						)


if __name__ == "__main__":
					import doctest

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












'''simple docstring'''
a__							:							Optional[Any] =256
# Modulus to hash a string
a__							:							Dict =1_000_003
def 				lowercase__   (   __lowercase						:  str				,  __lowercase						:  str     ) ->      bool:



       """simple docstring"""






       __UpperCamelCase       =  len(__lowercase     )
       __UpperCamelCase       =  len(__lowercase     )
       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(__lowercase     ):
              __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 				lowercase__   (   ) ->      None:



       """simple docstring"""






       __UpperCamelCase       =  'abc1abc12'
       __UpperCamelCase       =  'alskfjaldsabc1abc1abc12k23adsfabcabc'
       __UpperCamelCase       =  'alskfjaldsk23adsfabcabc'
       assert rabin_karp(__lowercase				,  __lowercase     ) and not rabin_karp(__lowercase				,  __lowercase     )

       # Test 2)
       __UpperCamelCase       =  'ABABX'
       __UpperCamelCase       =  'ABABZABABYABABX'
       assert rabin_karp(__lowercase				,  __lowercase     )

       # Test 3)
       __UpperCamelCase       =  'AAAB'
       __UpperCamelCase       =  'ABAAAAAB'
       assert rabin_karp(__lowercase				,  __lowercase     )

       # Test 4)
       __UpperCamelCase       =  'abcdabcy'
       __UpperCamelCase       =  'abcxabcdabxabcdabcdabcy'
       assert rabin_karp(__lowercase				,  __lowercase     )

       # Test 5)
       __UpperCamelCase       =  'Lü'
       __UpperCamelCase       =  'Lüsai'
       assert rabin_karp(__lowercase				,  __lowercase     )
       __UpperCamelCase       =  'Lue'
       assert not rabin_karp(__lowercase				,  __lowercase     )
       print('Success.'     )


if __name__ == "__main__":
    test_rabin_karp()
