from collections.abc import Sequence
from queue import Queue






class      __lowercase					:

						def __init__(	self				:      int							,							__lowerCamelCase				:      List[str]							,							__lowerCamelCase				:      Union[str, Any]							,							__lowerCamelCase				:      Union[str, Any]							,							__lowerCamelCase				:      Tuple=None							,							__lowerCamelCase				:      str=None   ):


									'''simple docstring'''

									lowercase							=		start
									lowercase							=		end
									lowercase							=		val
									lowercase							=		(start + end) // 2
									lowercase							=		left
									lowercase							=		right



						def __repr__(	self				:      List[Any]   ):


									'''simple docstring'''

									return f'SegmentTreeNode(start={self.start}, end={self.end}, val={self.val})'






class      __lowercase					:

						def __init__(	self				:      int							,							__lowerCamelCase				:      Sequence							,							__lowerCamelCase				:      Optional[Any]   ):


									'''simple docstring'''

									lowercase							=		collection
									lowercase							=		function
									if self.collection:
												lowercase							=		self._build_tree(0							,							len(__a   ) - 1   )

						def        __a		(	self				:      List[Any]							,							__lowerCamelCase				:      Tuple							,							__lowerCamelCase				:      Union[str, Any]   ):


									'''simple docstring'''

									self._update_tree(self.root							,							__a							,							__a   )

						def        __a		(	self				:      Any							,							__lowerCamelCase				:      List[str]							,							__lowerCamelCase				:      Optional[int]   ):


									'''simple docstring'''

									return self._query_range(self.root							,							__a							,							__a   )

						def        __a		(	self				:      List[Any]							,							__lowerCamelCase				:      str							,							__lowerCamelCase				:      Dict   ):


									'''simple docstring'''

									if start == end:
												return SegmentTreeNode(__a							,							__a							,							self.collection[start]   )
									lowercase							=		(start + end) // 2
									lowercase							=		self._build_tree(__a							,							__a   )
									lowercase							=		self._build_tree(mid + 1							,							__a   )
									return SegmentTreeNode(__a							,							__a							,							self.fn(left.val							,							right.val   )							,							__a							,							__a   )

						def        __a		(	self				:      Union[str, Any]							,							__lowerCamelCase				:      Dict							,							__lowerCamelCase				:      str							,							__lowerCamelCase				:      Optional[Any]   ):


									'''simple docstring'''

									if node.start == i and node.end == i:
												lowercase							=		val
												return
									if i <= node.mid:
												self._update_tree(node.left							,							__a							,							__a   )
									else:
												self._update_tree(node.right							,							__a							,							__a   )
									lowercase							=		self.fn(node.left.val							,							node.right.val   )

						def        __a		(	self				:      Tuple							,							__lowerCamelCase				:      Dict							,							__lowerCamelCase				:      Optional[Any]							,							__lowerCamelCase				:      int   ):


									'''simple docstring'''

									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							,							__a							,							__a   )
												else:
															# range in left child tree and right child tree
															return self.fn(
															    self._query_range(node.left							,							__a							,							node.mid   )							,							self._query_range(node.right							,							node.mid + 1							,							__a   )							,							)
									else:
												# range in right child tree
												return self._query_range(node.right							,							__a							,							__a   )



						def        __a		(	self				:      List[Any]   ):


									'''simple docstring'''

									if self.root is not None:
												lowercase							=		Queue()
												queue.put(self.root   )
												while not queue.empty():
															lowercase							=		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)
												A_      =      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()






from __future__ import annotations

from collections import deque






class      __lowercase					:

						def __init__(	self				:      Dict							,							__lowerCamelCase				:      list[str]   )							->		List[str]:


									'''simple docstring'''

									lowercase							=		[]
									self.adlist.append(
									    {'''value''': '''''', '''next_states''': [], '''fail_state''': 0, '''output''': []}   )

									for keyword in keywords:
												self.add_keyword(__lowerCamelCase   )
									self.set_fail_transitions()

						def        __a		(	self				:      str							,							__lowerCamelCase				:      int							,							__lowerCamelCase				:      str   )							->		int | None:


									'''simple docstring'''

									for state in self.adlist[current_state]["next_states"]:
												if char == self.adlist[state]["value"]:
															return state
									return None

						def        __a		(	self				:      List[Any]							,							__lowerCamelCase				:      str   )							->		None:


									'''simple docstring'''

									lowercase							=		0
									for character in keyword:
												lowercase							=		self.find_next_state(__lowerCamelCase							,							__lowerCamelCase   )
												if next_state is None:
															self.adlist.append(
															    {
															        '''value''': character,
															        '''next_states''': [],
															        '''fail_state''': 0,
															        '''output''': [],
															    }   )
															self.adlist[current_state]["next_states"].append(len(self.adlist   ) - 1   )
															lowercase							=		len(self.adlist   ) - 1
												else:
															lowercase							=		next_state
									self.adlist[current_state]["output"].append(__lowerCamelCase   )

						def        __a		(	self				:      int   )							->		None:


									'''simple docstring'''

									lowercase							=		deque()
									for node in self.adlist[0]["next_states"]:
												q.append(__lowerCamelCase   )
												lowercase							=		0
									while q:
												lowercase							=		q.popleft()
												for child in self.adlist[r]["next_states"]:
															q.append(__lowerCamelCase   )
															lowercase							=		self.adlist[r]['''fail_state''']
															while (
															    self.find_next_state(__lowerCamelCase							,							self.adlist[child]['''value''']   ) is None
															    and state != 0
															):
																		lowercase							=		self.adlist[state]['''fail_state''']
															lowercase							=		self.find_next_state(
															    __lowerCamelCase							,							self.adlist[child]['''value''']   )
															if self.adlist[child]["fail_state"] is None:
																		lowercase							=		0
															lowercase							=		(
															    self.adlist[child]['''output''']
															    + self.adlist[self.adlist[child]['''fail_state''']]['''output''']
															)



						def        __a		(	self				:      List[str]							,							__lowerCamelCase				:      str   )							->		dict[str, list[int]]:


									'''simple docstring'''

									lowercase							=		{}  # returns a dict with keywords and list of its occurrences
									lowercase							=		0
									for i in range(len(__lowerCamelCase   )   ):
												while (
												    self.find_next_state(__lowerCamelCase							,							string[i]   ) is None
												    and current_state != 0
												):
															lowercase							=		self.adlist[current_state]['''fail_state''']
												lowercase							=		self.find_next_state(__lowerCamelCase							,							string[i]   )
												if next_state is None:
															lowercase							=		0
												else:
															lowercase							=		next_state
															for key in self.adlist[current_state]["output"]:
																		if key not in result:
																					lowercase							=		[]
																		result[key].append(i - len(__lowerCamelCase   ) + 1   )
									return result


if __name__ == "__main__":
						import doctest

						doctest.testmod()





