





_lowerCamelCase			       =      256
# Modulus to hash a string
_lowerCamelCase			       =      100_0003




def    __UpperCAmelCase(      lowercase_ ,    lowercase_      ):
       _lowerCamelCase							:     Tuple	=		len(lowercase_      )
       _lowerCamelCase							:     int	=		len(lowercase_      )
       if p_len > t_len:
              return False

       _lowerCamelCase							:     Union[str, Any]	=		0
       _lowerCamelCase							:     int	=		0
       _lowerCamelCase							:     Union[str, Any]	=		1

       # Calculating the hash of pattern and substring of text
       for i in range(lowercase_      ):
              _lowerCamelCase							:     List[str]	=		(ord(pattern[i]      ) + p_hash * alphabet_size) % modulus
              _lowerCamelCase							:     Tuple	=		(ord(text[i]      ) + text_hash * alphabet_size) % modulus
              if i == p_len - 1:
                     continue
              _lowerCamelCase							:     List[str]	=		(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
              _lowerCamelCase							:     Optional[Any]	=		(
                  (text_hash - ord(text[i]      ) * modulus_power) * alphabet_size
                  + ord(text[i + p_len]      )
              ) % modulus
       return False




def    __UpperCAmelCase(      ):
       _lowerCamelCase							:     List[Any]	=		'''abc1abc12'''
       _lowerCamelCase							:     str	=		'''alskfjaldsabc1abc1abc12k23adsfabcabc'''
       _lowerCamelCase							:     int	=		'''alskfjaldsk23adsfabcabc'''
       assert rabin_karp(lowercase_ ,    lowercase_      ) and not rabin_karp(lowercase_ ,    lowercase_      )

       # Test 2)
       _lowerCamelCase							:     List[Any]	=		'''ABABX'''
       _lowerCamelCase							:     Any	=		'''ABABZABABYABABX'''
       assert rabin_karp(lowercase_ ,    lowercase_      )

       # Test 3)
       _lowerCamelCase							:     str	=		'''AAAB'''
       _lowerCamelCase							:     Union[str, Any]	=		'''ABAAAAAB'''
       assert rabin_karp(lowercase_ ,    lowercase_      )

       # Test 4)
       _lowerCamelCase							:     Dict	=		'''abcdabcy'''
       _lowerCamelCase							:     int	=		'''abcxabcdabxabcdabcdabcy'''
       assert rabin_karp(lowercase_ ,    lowercase_      )

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


if __name__ == "__main__":
       test_rabin_karp()








def    __UpperCAmelCase(      lowercase_      ):
       # if the collection is empty, returns empty
       if collection == []:
              return []

       # get some information about the collection
       _lowerCamelCase							:     Tuple	=		len(lowercase_      )
       _lowerCamelCase							:     List[str]	=		max(lowercase_      )
       _lowerCamelCase							:     Any	=		min(lowercase_      )

       # create the counting array
       _lowerCamelCase							:     str	=		coll_max + 1 - coll_min
       _lowerCamelCase							:     Union[str, Any]	=		[0] * counting_arr_length

       # count how much a number appears in the collection
       for number in collection:
              counting_arr[number - coll_min] += 1

       # sum each position with it's predecessors. now, counting_arr[i] tells
       # us how many elements <= i has in the collection
       for i in range(1 ,    lowercase_      ):
              _lowerCamelCase							:     Union[str, Any]	=		counting_arr[i] + counting_arr[i - 1]

       # create the output collection
       _lowerCamelCase							:     Dict	=		[0] * coll_len

       # place the elements in the output, respecting the original order (stable
       # sort) from end to begin, updating counting_arr
       for i in reversed(range(0 ,    lowercase_      )      ):
              _lowerCamelCase							:     Union[str, Any]	=		collection[i]
              counting_arr[collection[i] - coll_min] -= 1

       return ordered




def    __UpperCAmelCase(      lowercase_      ):
       return "".join([chr(lowercase_      ) for i in counting_sort([ord(lowercase_      ) for c in string]      )]      )


if __name__ == "__main__":
       # Test string sort
       assert counting_sort_string('thisisthestring') == "eghhiiinrsssttt"

       _lowerCamelCase			       =      input('Enter numbers separated by a comma:\n').strip()
       _lowerCamelCase			       =      [int(item) for item in user_input.split(',')]
       print(counting_sort(unsorted))

