
'''simple docstring'''







from copy import deepcopy


class 						__UpperCAmelCase      :


							def __init__(       self    ,   lowerCAmelCase_ = None    ,   lowerCAmelCase_ = None  ):





								"""simple docstring"""






								if arr is None and size is not None:
									_snake_case   						=		size
									_snake_case   						=		[0] * size
								elif arr is not None:
									self.init(lowerCAmelCase_  )
								else:
									raise ValueError('Either arr or size must be specified'  )


							def  lowerCamelCase				(       self    ,   lowerCAmelCase_  ):





								"""simple docstring"""






								_snake_case   						=		len(lowerCAmelCase_  )
								_snake_case   						=		deepcopy(lowerCAmelCase_  )
								for i in range(1    ,   self.size  ):
									_snake_case   						=		self.next_(lowerCAmelCase_  )
									if j < self.size:
										self.tree[j] += self.tree[i]


							def  lowerCamelCase				(       self  ):





								"""simple docstring"""






								_snake_case   						=		self.tree[:]
								for i in range(self.size - 1    ,   0    ,   -1  ):
									_snake_case   						=		self.next_(lowerCAmelCase_  )
									if j < self.size:
										arr[j] -= arr[i]
								return arr


							@staticmethod
							def  lowerCamelCase				(       lowerCAmelCase_  ):





								"""simple docstring"""






								return index + (index & (-index))


							@staticmethod
							def  lowerCamelCase				(       lowerCAmelCase_  ):





								"""simple docstring"""






								return index - (index & (-index))


							def  lowerCamelCase				(       self    ,   lowerCAmelCase_    ,   lowerCAmelCase_  ):





								"""simple docstring"""






								if index == 0:
									self.tree[0] += value
									return
								while index < self.size:
									self.tree[index] += value
									_snake_case   						=		self.next_(lowerCAmelCase_  )


							def  lowerCamelCase				(       self    ,   lowerCAmelCase_    ,   lowerCAmelCase_  ):





								"""simple docstring"""






								self.add(lowerCAmelCase_    ,   value - self.get(lowerCAmelCase_  )  )


							def  lowerCamelCase				(       self    ,   lowerCAmelCase_  ):





								"""simple docstring"""






								if right == 0:
									return 0
								_snake_case   						=		self.tree[0]
								right -= 1  # make right inclusive
								while right > 0:
									result += self.tree[right]
									_snake_case   						=		self.prev(lowerCAmelCase_  )
								return result


							def  lowerCamelCase				(       self    ,   lowerCAmelCase_    ,   lowerCAmelCase_  ):





								"""simple docstring"""






								return self.prefix(lowerCAmelCase_  ) - self.prefix(lowerCAmelCase_  )


							def  lowerCamelCase				(       self    ,   lowerCAmelCase_  ):





								"""simple docstring"""






								return self.query(lowerCAmelCase_    ,   index + 1  )




							def  lowerCamelCase				(       self    ,   lowerCAmelCase_  ):





								"""simple docstring"""






								value -= self.tree[0]
								if value < 0:
									return -1

								_snake_case   						=		1  # Largest power of 2 <= size
								while j * 2 < self.size:
									j *= 2

								_snake_case   						=		0

								while j > 0:
									if i + j < self.size and self.tree[i + j] <= value:
										value -= self.tree[i + j]
										i += j
									j //= 2
								return i


if __name__ == "__main__":
					import doctest

					doctest.testmod()







def      A      (      _SCREAMING_SNAKE_CASE ,_SCREAMING_SNAKE_CASE    )	-> list:
       lowerCamelCase   :      Dict			 =					len(_SCREAMING_SNAKE_CASE    )
       lowerCamelCase   :      Union[str, Any]			 =					[]
       for i in range(len(_SCREAMING_SNAKE_CASE    ) - pat_len + 1    ):
              lowerCamelCase   :      Dict			 =					True
              for j in range(_SCREAMING_SNAKE_CASE    ):
                     if s[i + j] != pattern[j]:
                            lowerCamelCase   :      Optional[int]			 =					False
                            break
              if match_found:
                     position.append(_SCREAMING_SNAKE_CASE    )
       return position


if __name__ == "__main__":
       assert naive_pattern_search('ABCDEFG', 'DE') == [3]
       print(naive_pattern_search('ABAAABCDBBABCDDEBCABC', 'ABC'))






