






from collections.abc import Sequence
from queue import Queue


class   __SCREAMING_SNAKE_CASE:
							def __init__(     self:      Dict       ,	UpperCamelCase:      List[str]       ,	UpperCamelCase:      Tuple       ,	UpperCamelCase:      Optional[Any]       ,	UpperCamelCase:      Dict=None       ,	UpperCamelCase:      Optional[Any]=None						)		->		Tuple:
											snake_case__									=     start
											snake_case__									=     end
											snake_case__									=     val
											snake_case__									=     (start + end) // 2
											snake_case__									=     left
											snake_case__									=     right


							def __repr__(     self:      List[Any]						)		->		str:
											return F'''SegmentTreeNode(start={self.start}, end={self.end}, val={self.val})'''


class   __SCREAMING_SNAKE_CASE:
							def __init__(     self:      List[Any]       ,	UpperCamelCase:      Dict       ,	UpperCamelCase:      int						)		->		Optional[Any]:
											snake_case__									=     collection
											snake_case__									=     function
											if self.collection:
															snake_case__									=     self._build_tree(0       ,	len(UpperCAmelCase_						) - 1						)
							def lowerCAmelCase_ (     self:      Tuple       ,	UpperCamelCase:      int       ,	UpperCamelCase:      List[str]						)		->		str:
											self._update_tree(self.root       ,	UpperCAmelCase_       ,	UpperCAmelCase_						)
							def lowerCAmelCase_ (     self:      str       ,	UpperCamelCase:      List[Any]       ,	UpperCamelCase:      List[Any]						)		->		Union[str, Any]:
											return self._query_range(self.root       ,	UpperCAmelCase_       ,	UpperCAmelCase_						)
							def lowerCAmelCase_ (     self:      Optional[int]       ,	UpperCamelCase:      List[str]       ,	UpperCamelCase:      List[Any]						)		->		List[str]:
											if start == end:
															return SegmentTreeNode(UpperCAmelCase_       ,	UpperCAmelCase_       ,	self.collection[start]						)
											snake_case__									=     (start + end) // 2
											snake_case__									=     self._build_tree(UpperCAmelCase_       ,	UpperCAmelCase_						)
											snake_case__									=     self._build_tree(mid + 1       ,	UpperCAmelCase_						)
											return SegmentTreeNode(UpperCAmelCase_       ,	UpperCAmelCase_       ,	self.fn(left.val       ,	right.val						)       ,	UpperCAmelCase_       ,	UpperCAmelCase_						)
							def lowerCAmelCase_ (     self:      Tuple       ,	UpperCamelCase:      Optional[int]       ,	UpperCamelCase:      int       ,	UpperCamelCase:      int						)		->		List[Any]:
											if node.start == i and node.end == i:
															snake_case__									=     val
															return
											if i <= node.mid:
															self._update_tree(node.left       ,	UpperCAmelCase_       ,	UpperCAmelCase_						)
											else:
															self._update_tree(node.right       ,	UpperCAmelCase_       ,	UpperCAmelCase_						)
											snake_case__									=     self.fn(node.left.val       ,	node.right.val						)
							def lowerCAmelCase_ (     self:      Union[str, Any]       ,	UpperCamelCase:      str       ,	UpperCamelCase:      List[Any]       ,	UpperCamelCase:      str						)		->		Optional[int]:
											if node.start == i and node.end == j:
															return node.val

											if i <= node.mid:
															if j <= node.mid:
																			# range in left child tree
																			return self._query_range(node.left       ,	UpperCAmelCase_       ,	UpperCAmelCase_						)
															else:
																			# range in left child tree and right child tree
																			return self.fn(
																			    self._query_range(node.left       ,	UpperCAmelCase_       ,	node.mid						)       ,	self._query_range(node.right       ,	node.mid + 1       ,	UpperCAmelCase_						)       ,	)
											else:
															# range in right child tree
															return self._query_range(node.right       ,	UpperCAmelCase_       ,	UpperCAmelCase_						)


							def lowerCAmelCase_ (     self:      Tuple						)		->		Dict:
											if self.root is not None:
															snake_case__									=     Queue()
															queue.put(self.root						)
															while not queue.empty():
																			snake_case__									=     queue.get()
																			yield node

																			if node.left is not None:
																							queue.put(node.left						)

																			if node.right is not None:
																							queue.put(node.right						)


if __name__ == "__main__":
							import operator

							for fn in [operator.add, max, min]:
														print("""*""" * 50)
														__UpperCamelCase					:		int	  =						SegmentTree([2, 1, 5, 3, 4], fn)
														for node in arr.traverse():
																					print(node)
														print()

														arr.update(1, 5)
														for node in arr.traverse():
																					print(node)
														print()

														print(arr.query_range(3, 4))  # 7
														print(arr.query_range(2, 2))  # 5
														print(arr.query_range(1, 3))  # 13
														print()












__UpperCamelCase					:		List[str]	  =						256
# Modulus to hash a string
__UpperCamelCase					:		int	  =						1000003
def      a_ (      _A      ,   _A  )			->			bool:







				"""simple docstring"""
				snake_case__									=     len(_A  )
				snake_case__									=     len(_A  )
				if p_len > t_len:
								return False

				snake_case__									=     0
				snake_case__									=     0
				snake_case__									=     1

				# Calculating the hash of pattern and substring of text
				for i in range(_A  ):
								snake_case__									=     (ord(pattern[i]  ) + p_hash * alphabet_size) % modulus
								snake_case__									=     (ord(text[i]  ) + text_hash * alphabet_size) % modulus
								if i == p_len - 1:
												continue
								snake_case__									=     (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
								snake_case__									=     (
								    (text_hash - ord(text[i]  ) * modulus_power) * alphabet_size
								    + ord(text[i + p_len]  )
								) % modulus
				return False
def      a_ (      )			->			None:







				"""simple docstring"""
				snake_case__									=     'abc1abc12'
				snake_case__									=     'alskfjaldsabc1abc1abc12k23adsfabcabc'
				snake_case__									=     'alskfjaldsk23adsfabcabc'
				assert rabin_karp(_A      ,   _A  ) and not rabin_karp(_A      ,   _A  )

				# Test 2)
				snake_case__									=     'ABABX'
				snake_case__									=     'ABABZABABYABABX'
				assert rabin_karp(_A      ,   _A  )

				# Test 3)
				snake_case__									=     'AAAB'
				snake_case__									=     'ABAAAAAB'
				assert rabin_karp(_A      ,   _A  )

				# Test 4)
				snake_case__									=     'abcdabcy'
				snake_case__									=     'abcxabcdabxabcdabcdabcy'
				assert rabin_karp(_A      ,   _A  )

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


if __name__ == "__main__":
							test_rabin_karp()




