






from __future__ import annotations

from collections import deque



class   lowerCamelCase				:







		'''simple docstring'''



		def __init__(							self    ,		_UpperCamelCase       )     ->							Dict:
							UpperCAmelCase_   :				list[dict]						=				[]
							self.adlist.append(
							    {'value': '', 'next_states': [], 'fail_state': 0, 'output': []}       )

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



		def  __UpperCAmelCase      (							self    ,		_UpperCamelCase    ,		_UpperCamelCase       )     ->							int | None:
							for state in self.adlist[current_state]["next_states"]:
												if char == self.adlist[state]["value"]:
																	return state
							return None



		def  __UpperCAmelCase      (							self    ,		_UpperCamelCase       )     ->							None:
							UpperCAmelCase_   :				Union[str, Any]						=				0
							for character in keyword:
												UpperCAmelCase_   :				Optional[Any]						=				self.find_next_state(_UpperCamelCase    ,		_UpperCamelCase       )
												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       )
																	UpperCAmelCase_   :				List[Any]						=				len(self.adlist       ) - 1
												else:
																	UpperCAmelCase_   :				Tuple						=				next_state
							self.adlist[current_state]["output"].append(_UpperCamelCase       )



		def  __UpperCAmelCase      (							self       )     ->							None:
							UpperCAmelCase_   :				deque						=				deque()
							for node in self.adlist[0]["next_states"]:
												q.append(_UpperCamelCase       )
												UpperCAmelCase_   :				Tuple						=				0
							while q:
												UpperCAmelCase_   :				int						=				q.popleft()
												for child in self.adlist[r]["next_states"]:
																	q.append(_UpperCamelCase       )
																	UpperCAmelCase_   :				Tuple						=				self.adlist[r]['fail_state']
																	while (
																	    self.find_next_state(_UpperCamelCase    ,		self.adlist[child]['value']       ) is None
																	    and state != 0
																	):
																						UpperCAmelCase_   :				Dict						=				self.adlist[state]['fail_state']
																	UpperCAmelCase_   :				Optional[int]						=				self.find_next_state(
																	    _UpperCamelCase    ,		self.adlist[child]['value']       )
																	if self.adlist[child]["fail_state"] is None:
																						UpperCAmelCase_   :				Optional[Any]						=				0
																	UpperCAmelCase_   :				Tuple						=				(
																	    self.adlist[child]['output']
																	    + self.adlist[self.adlist[child]['fail_state']]['output']
																	)



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


if __name__ == "__main__":
		import doctest

		doctest.testmod()














from __future__ import annotations




def 					lowercase__				(					__snake_case   :							list[int]					,	__snake_case   :							int  ):


					'''simple docstring'''


					if len(__snake_case  ) < k or k < 0:
										raise ValueError('Invalid Input'  )
					UpperCAmelCase_   :				int						=						sum(array[:k]  )
					for i in range(len(__snake_case  ) - k  ):
										UpperCAmelCase_   :				List[Any]						=						current_sum - array[i] + array[i + k]
										UpperCAmelCase_   :				List[Any]						=						max(__snake_case					,	__snake_case  )
					return max_sum


if __name__ == "__main__":
		from doctest import testmod
		from random import randint

		testmod()
		__UpperCAmelCase     							=						[randint(-1000, 1000) for i in range(100)]
		__UpperCAmelCase     							=						randint(0, 110)
		print(F'The maximum sum of {k} consecutive elements is {max_sum_in_array(array,k)}')






