


'''simple docstring'''


from copy import deepcopy






class 		lowerCAmelCase__	:




			def __init__(						self     :   Tuple		,     lowerCamelCase__     :   list[int] | None = None		,     lowerCamelCase__     :   int | None = None       )      ->None:



					'''simple docstring'''







					if arr is None and size is not None:
							_UpperCAmelCase						:				Any	    =					size
							_UpperCAmelCase						:				List[str]	    =					[0] * size
					elif arr is not None:
							self.init(lowerCamelCase__       )
					else:
							raise ValueError("Either arr or size must be specified"       )




			def 							lowerCAmelCase__			(						self     :   str		,     lowerCamelCase__     :   list[int]       )      ->None:



					'''simple docstring'''







					_UpperCAmelCase						:				Any	    =					len(lowerCamelCase__       )
					_UpperCAmelCase						:				Dict	    =					deepcopy(lowerCamelCase__       )
					for i in range(1		,     self.size       ):
							_UpperCAmelCase						:				Dict	    =					self.next_(lowerCamelCase__       )
							if j < self.size:
									self.tree[j] += self.tree[i]




			def 							lowerCAmelCase__			(						self     :   List[Any]       )      ->list[int]:



					'''simple docstring'''







					_UpperCAmelCase						:				Dict	    =					self.tree[:]
					for i in range(self.size - 1		,     0		,     -1       ):
							_UpperCAmelCase						:				Union[str, Any]	    =					self.next_(lowerCamelCase__       )
							if j < self.size:
									arr[j] -= arr[i]
					return arr




			@staticmethod
			def 							lowerCAmelCase__			(						lowerCamelCase__     :   int       )      ->int:



					'''simple docstring'''







					return index + (index & (-index))




			@staticmethod
			def 							lowerCAmelCase__			(						lowerCamelCase__     :   int       )      ->int:



					'''simple docstring'''







					return index - (index & (-index))




			def 							lowerCAmelCase__			(						self     :   Union[str, Any]		,     lowerCamelCase__     :   int		,     lowerCamelCase__     :   int       )      ->None:



					'''simple docstring'''







					if index == 0:
							self.tree[0] += value
							return
					while index < self.size:
							self.tree[index] += value
							_UpperCAmelCase						:				Optional[Any]	    =					self.next_(lowerCamelCase__       )




			def 							lowerCAmelCase__			(						self     :   Tuple		,     lowerCamelCase__     :   int		,     lowerCamelCase__     :   int       )      ->None:



					'''simple docstring'''







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




			def 							lowerCAmelCase__			(						self     :   Union[str, Any]		,     lowerCamelCase__     :   int       )      ->int:



					'''simple docstring'''







					if right == 0:
							return 0
					_UpperCAmelCase						:				Union[str, Any]	    =					self.tree[0]
					right -= 1  # make right inclusive
					while right > 0:
							result += self.tree[right]
							_UpperCAmelCase						:				Tuple	    =					self.prev(lowerCamelCase__       )
					return result




			def 							lowerCAmelCase__			(						self     :   Optional[Any]		,     lowerCamelCase__     :   int		,     lowerCamelCase__     :   int       )      ->int:



					'''simple docstring'''







					return self.prefix(lowerCamelCase__       ) - self.prefix(lowerCamelCase__       )




			def 							lowerCAmelCase__			(						self     :   Dict		,     lowerCamelCase__     :   int       )      ->int:



					'''simple docstring'''







					return self.query(lowerCamelCase__		,     index + 1       )






			def 							lowerCAmelCase__			(						self     :   List[str]		,     lowerCamelCase__     :   int       )      ->int:



					'''simple docstring'''







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

					_UpperCAmelCase						:				Optional[int]	    =					1  # Largest power of 2 <= size
					while j * 2 < self.size:
							j *= 2

					_UpperCAmelCase						:				Optional[int]	    =					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()







'''simple docstring'''


import math






def        __lowerCAmelCase       (__lowerCAmelCase      ):
		return math.sqrt(__lowerCAmelCase      ) * math.sqrt(__lowerCAmelCase      ) == num






def        __lowerCAmelCase       (__lowerCAmelCase      ):
		_UpperCAmelCase						:				int	    =					0
		_UpperCAmelCase						:				Tuple	    =					n
		while left <= right:
				_UpperCAmelCase						:				int	    =					(left + right) // 2
				if mid**2 == n:
						return True
				elif mid**2 > n:
						_UpperCAmelCase						:				str	    =					mid - 1
				else:
						_UpperCAmelCase						:				List[str]	    =					mid + 1
		return False


if __name__ == "__main__":
						import doctest

						doctest.testmod()



