


'''simple docstring'''






__A					:  str											=      256
# Modulus to hash a string
__A					:  Tuple											=      100_0003







def 				UpperCamelCase_			(    A__					:   str							,    A__					:   str					):
  '''simple docstring'''





  lowerCAmelCase_			:      List[str]			=   len(A__					)
  lowerCAmelCase_			:      int			=   len(A__					)
  if p_len > t_len:
    return False

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

  # Calculating the hash of pattern and substring of text
  for i in range(A__					):
    lowerCAmelCase_			:      Tuple			=   (ord(pattern[i]					) + p_hash * alphabet_size) % modulus
    lowerCAmelCase_			:      Dict			=   (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[int]			=   (
        (text_hash - ord(text[i]					) * modulus_power) * alphabet_size
        + ord(text[i + p_len]					)
    ) % modulus
  return False







def 				UpperCamelCase_			(    ):
  '''simple docstring'''





  lowerCAmelCase_			:      Optional[int]			=   """abc1abc12"""
  lowerCAmelCase_			:      str			=   """alskfjaldsabc1abc1abc12k23adsfabcabc"""
  lowerCAmelCase_			:      Union[str, Any]			=   """alskfjaldsk23adsfabcabc"""
  assert rabin_karp(A__							,    A__					) and not rabin_karp(A__							,    A__					)

  # Test 2)
  lowerCAmelCase_			:      Dict			=   """ABABX"""
  lowerCAmelCase_			:      List[Any]			=   """ABABZABABYABABX"""
  assert rabin_karp(A__							,    A__					)

  # Test 3)
  lowerCAmelCase_			:      List[str]			=   """AAAB"""
  lowerCAmelCase_			:      Any			=   """ABAAAAAB"""
  assert rabin_karp(A__							,    A__					)

  # Test 4)
  lowerCAmelCase_			:      Optional[int]			=   """abcdabcy"""
  lowerCAmelCase_			:      Optional[Any]			=   """abcxabcdabxabcdabcdabcy"""
  assert rabin_karp(A__							,    A__					)

  # Test 5)
  lowerCAmelCase_			:      Optional[Any]			=   """Lü"""
  lowerCAmelCase_			:      Optional[Any]			=   """Lüsai"""
  assert rabin_karp(A__							,    A__					)
  lowerCAmelCase_			:      int			=   """Lue"""
  assert not rabin_karp(A__							,    A__					)
  print("""Success."""					)


if __name__ == "__main__":
  test_rabin_karp()







'''simple docstring'''






def 				UpperCamelCase_			(    A__					:   int					):
  '''simple docstring'''





  lowerCAmelCase_			:      Union[str, Any]			=   (1 + 24 * n) ** 0.5
  return ((1 + root) / 6) % 1 == 0







def 				UpperCamelCase_			(    A__					:   int = 50_00					):
  '''simple docstring'''





  lowerCAmelCase_			:      Optional[int]			=   [(i * (3 * i - 1)) // 2 for i in range(1							,    A__					)]
  for i, pentagonal_i in enumerate(A__					):
    for j in range(A__							,    len(A__					)					):
      lowerCAmelCase_			:      int			=   pentagonal_nums[j]
      lowerCAmelCase_			:      Union[str, Any]			=   pentagonal_i + pentagonal_j
      lowerCAmelCase_			:      List[Any]			=   pentagonal_j - pentagonal_i
      if is_pentagonal(A__					) and is_pentagonal(A__					):
        return b

  return -1


if __name__ == "__main__":
  print(F'''{solution() = }''')



