






"""simple docstring"""





from __future__ import annotations

from collections import deque



class       __A		:

					def __init__(			self  :      List[str]     ,		__snake_case  :      list[str]					)			->							Optional[Any]:
											__magic_name__:	list[dict]							=       []
											self.adlist.append(
											    {"""value""": """""", """next_states""": [], """fail_state""": 0, """output""": []}					)

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

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

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

					def   lowerCamelCase__   (			self  :      List[str]					)			->							None:
											__magic_name__:	deque							=       deque()
											for node in self.adlist[0]["next_states"]:
																	q.append(__snake_case					)
																	__magic_name__:	Optional[int]							=       0
											while q:
																	__magic_name__:	Any							=       q.popleft()
																	for child in self.adlist[r]["next_states"]:
																							q.append(__snake_case					)
																							__magic_name__:	str							=       self.adlist[r]["""fail_state"""]
																							while (
																							    self.find_next_state(__snake_case     ,		self.adlist[child]["""value"""]					) is None
																							    and state != 0
																							):
																													__magic_name__:	Dict							=       self.adlist[state]["""fail_state"""]
																							__magic_name__:	Union[str, Any]							=       self.find_next_state(
																							    __snake_case     ,		self.adlist[child]["""value"""]					)
																							if self.adlist[child]["fail_state"] is None:
																													__magic_name__:	Optional[int]							=       0
																							__magic_name__:	int							=       (
																							    self.adlist[child]["""output"""]
																							    + self.adlist[self.adlist[child]["""fail_state"""]]["""output"""]
																							)






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


if __name__ == "__main__":
							import doctest

							doctest.testmod()









from __future__ import annotations
def 		a_							( __lowerCAmelCase				):
  if not nums:
    return 0
  lowerCAmelCase__										=      nums[0]
  lowerCAmelCase__										=      0
  for num in nums[1:]:
    lowerCAmelCase__				,      lowerCAmelCase__										=      (
        max_excluding + num,
        max(__lowerCAmelCase   , __lowerCAmelCase				),
    )
  return max(__lowerCAmelCase   , __lowerCAmelCase				)


if __name__ == "__main__":
      import doctest

      doctest.testmod()

