


'''simple docstring'''


class 	lowerCAmelCase__			:




			def __init__(					self  :     Tuple	,  lowerCamelCase__  :     Union[str, Any]	,  lowerCamelCase__  :     Any )   ->Optional[Any]:



					'''simple docstring'''







					_UpperCAmelCase		:       Tuple								=      name
					_UpperCAmelCase		:       List[str]								=      val




			def __str__(					self  :     Union[str, Any] )   ->List[Any]:



					'''simple docstring'''







					return F"""{self.__class__.__name__}({self.name}, {self.val})"""






			def __lt__(					self  :     Optional[Any]	,  lowerCamelCase__  :     Union[str, Any] )   ->str:



					'''simple docstring'''







					return self.val < other.val






class 	lowerCAmelCase__			:




			def __init__(					self  :     Tuple	,  lowerCamelCase__  :     Union[str, Any] )   ->Tuple:



					'''simple docstring'''







					_UpperCAmelCase		:       Dict								=      {}
					_UpperCAmelCase		:       Any								=      {}
					_UpperCAmelCase		:       Tuple								=      self.build_heap(lowerCamelCase__ )




			def __getitem__(					self  :     Union[str, Any]	,  lowerCamelCase__  :     Dict )   ->Dict:



					'''simple docstring'''







					return self.get_value(lowerCamelCase__ )




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



					'''simple docstring'''







					return (idx - 1) // 2




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



					'''simple docstring'''







					return idx * 2 + 1




			def 							lowerCAmelCase__    (					self  :     str	,  lowerCamelCase__  :     Tuple )   ->Dict:



					'''simple docstring'''







					return idx * 2 + 2




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



					'''simple docstring'''







					return self.heap_dict[key]




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



					'''simple docstring'''







					_UpperCAmelCase		:       Union[str, Any]								=      len(lowerCamelCase__ ) - 1
					_UpperCAmelCase		:       List[str]								=      self.get_parent_idx(lowerCamelCase__ )

					for idx, i in enumerate(lowerCamelCase__ ):
							_UpperCAmelCase		:       List[str]								=      idx
							_UpperCAmelCase		:       Tuple								=      i.val

					for i in range(lowerCamelCase__	,  -1	,  -1 ):
							self.sift_down(lowerCamelCase__	,  lowerCamelCase__ )
					return array




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



					'''simple docstring'''







					while True:
							_UpperCAmelCase		:       List[Any]								=      self.get_left_child_idx(lowerCamelCase__ )  # noqa: E741
							_UpperCAmelCase		:       Dict								=      self.get_right_child_idx(lowerCamelCase__ )

							_UpperCAmelCase		:       int								=      idx
							if l < len(lowerCamelCase__ ) and array[l] < array[idx]:
									_UpperCAmelCase		:       Optional[int]								=      l
							if r < len(lowerCamelCase__ ) and array[r] < array[smallest]:
									_UpperCAmelCase		:       Optional[int]								=      r

							if smallest != idx:
									_UpperCAmelCase		:       int								=      array[smallest], array[idx]
									(
									    _UpperCAmelCase    
									)		:       Optional[int]								=      (
									    self.idx_of_element[array[smallest]],
									    self.idx_of_element[array[idx]],
									)
									_UpperCAmelCase		:       Union[str, Any]								=      smallest
							else:
									break




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



					'''simple docstring'''







					_UpperCAmelCase		:       List[str]								=      self.get_parent_idx(lowerCamelCase__ )
					while p >= 0 and self.heap[p] > self.heap[idx]:
							_UpperCAmelCase		:       Optional[int]								=      self.heap[idx], self.heap[p]
							_UpperCAmelCase		:       Dict								=      (
							    self.idx_of_element[self.heap[idx]],
							    self.idx_of_element[self.heap[p]],
							)
							_UpperCAmelCase		:       Optional[int]								=      p
							_UpperCAmelCase		:       str								=      self.get_parent_idx(lowerCamelCase__ )




			def 							lowerCAmelCase__    (					self  :     Dict )   ->Optional[Any]:



					'''simple docstring'''







					return self.heap[0]




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



					'''simple docstring'''







					_UpperCAmelCase		:       Dict								=      self.heap[-1], self.heap[0]
					_UpperCAmelCase		:       Tuple								=      (
					    self.idx_of_element[self.heap[-1]],
					    self.idx_of_element[self.heap[0]],
					)

					_UpperCAmelCase		:       int								=      self.heap.pop()
					del self.idx_of_element[x]
					self.sift_down(0	,  self.heap )
					return x




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



					'''simple docstring'''







					self.heap.append(lowerCamelCase__ )
					_UpperCAmelCase		:       int								=      len(self.heap ) - 1
					_UpperCAmelCase		:       int								=      node.val
					self.sift_up(len(self.heap ) - 1 )




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



					'''simple docstring'''







					return len(self.heap ) == 0






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



					'''simple docstring'''







					assert (
					    self.heap[self.idx_of_element[node]].val > new_value
					), "newValue must be less that current value"
					_UpperCAmelCase		:       int								=      new_value
					_UpperCAmelCase		:       Union[str, Any]								=      new_value
					self.sift_up(self.idx_of_element[node] )




lowerCamelCase__    	=     Node('R', -1)
lowerCamelCase__    	=     Node('B', 6)
lowerCamelCase__    	=     Node('A', 3)
lowerCamelCase__    	=     Node('X', 1)
lowerCamelCase__    	=     Node('E', 4)

# Use one of these two ways to generate Min-Heap

# Generating Min-Heap from array
lowerCamelCase__    	=     MinHeap([r, b, a, x, e])

# Generating Min-Heap by Insert method
# myMinHeap.insert(a)
# myMinHeap.insert(b)
# myMinHeap.insert(x)
# myMinHeap.insert(r)
# myMinHeap.insert(e)

# Before
print('Min Heap - before decrease key')
for i in my_min_heap.heap:
						print(i)

print('Min Heap - After decrease key of node [B -> -17]')
my_min_heap.decrease_key(b, -17)

# After
for i in my_min_heap.heap:
						print(i)

if __name__ == "__main__":
						import doctest

						doctest.testmod()







'''simple docstring'''


from math import factorial






class 	lowerCAmelCase__			:




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



					'''simple docstring'''







					_UpperCAmelCase		:       Optional[Any]								=      real
					if isinstance(lowerCamelCase__	,  lowerCamelCase__ ):
							_UpperCAmelCase		:       Any								=      [1] * rank
					else:
							_UpperCAmelCase		:       Dict								=      rank




			def __repr__(		self  :     str )   ->List[str]:



					'''simple docstring'''







					return (
					    F"""{self.real}+"""
					    F"""{'+'.join(str(lowerCamelCase__ )+'E'+str(n+1 )for n,dual in enumerate(self.duals ) )}"""
					)




			def 							lowerCAmelCase__    (		self  :     Dict )   ->Tuple:



					'''simple docstring'''







					_UpperCAmelCase		:       Union[str, Any]								=      self.duals.copy()
					while cur[-1] == 0:
							cur.pop(-1 )
					return Dual(self.real	,  lowerCamelCase__ )




			def __add__(		self  :     Dict	,  lowerCamelCase__  :     List[Any] )   ->Any:



					'''simple docstring'''







					if not isinstance(lowerCamelCase__	,  lowerCamelCase__ ):
							return Dual(self.real + other	,  self.duals )
					_UpperCAmelCase		:       Optional[int]								=      self.duals.copy()
					_UpperCAmelCase		:       Optional[int]								=      other.duals.copy()
					if len(lowerCamelCase__ ) > len(lowerCamelCase__ ):
							o_dual.extend([1] * (len(lowerCamelCase__ ) - len(lowerCamelCase__ )) )
					elif len(lowerCamelCase__ ) < len(lowerCamelCase__ ):
							s_dual.extend([1] * (len(lowerCamelCase__ ) - len(lowerCamelCase__ )) )
					_UpperCAmelCase		:       Union[str, Any]								=      []
					for i in range(len(lowerCamelCase__ ) ):
							new_duals.append(s_dual[i] + o_dual[i] )
					return Dual(self.real + other.real	,  lowerCamelCase__ )

			lowerCAmelCase :	Tuple          =     __add__




			def __sub__(		self  :     List[Any]	,  lowerCamelCase__  :     Union[str, Any] )   ->Dict:



					'''simple docstring'''







					return self + other * -1




			def __mul__(		self  :     List[str]	,  lowerCamelCase__  :     Optional[Any] )   ->Union[str, Any]:



					'''simple docstring'''







					if not isinstance(lowerCamelCase__	,  lowerCamelCase__ ):
							_UpperCAmelCase		:       Optional[int]								=      []
							for i in self.duals:
									new_duals.append(i * other )
							return Dual(self.real * other	,  lowerCamelCase__ )
					_UpperCAmelCase		:       Union[str, Any]								=      [0] * (len(self.duals ) + len(other.duals ) + 1)
					for i, item in enumerate(self.duals ):
							for j, jtem in enumerate(other.duals ):
									new_duals[i + j + 1] += item * jtem
					for k in range(len(self.duals ) ):
							new_duals[k] += self.duals[k] * other.real
					for index in range(len(other.duals ) ):
							new_duals[index] += other.duals[index] * self.real
					return Dual(self.real * other.real	,  lowerCamelCase__ )

			lowerCAmelCase :	Union[str, Any]          =     __mul__




			def __truediv__(		self  :     Optional[Any]	,  lowerCamelCase__  :     List[Any] )   ->Union[str, Any]:



					'''simple docstring'''







					if not isinstance(lowerCamelCase__	,  lowerCamelCase__ ):
							_UpperCAmelCase		:       Union[str, Any]								=      []
							for i in self.duals:
									new_duals.append(i / other )
							return Dual(self.real / other	,  lowerCamelCase__ )
					raise ValueError




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



					'''simple docstring'''







					if not isinstance(lowerCamelCase__	,  lowerCamelCase__ ):
							_UpperCAmelCase		:       Tuple								=      []
							for i in self.duals:
									new_duals.append(i // other )
							return Dual(self.real // other	,  lowerCamelCase__ )
					raise ValueError






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



					'''simple docstring'''







					if n < 0 or isinstance(lowerCamelCase__	,  lowerCamelCase__ ):
							raise ValueError("power must be a positive integer" )
					if n == 0:
							return 1
					if n == 1:
							return self
					_UpperCAmelCase		:       str								=      self
					for _ in range(n - 1 ):
							x *= self
					return x






def  __lowerCAmelCase (__lowerCAmelCase      , __lowerCAmelCase      , __lowerCAmelCase   ):
		if not callable(__lowerCAmelCase   ):
				raise ValueError("differentiate() requires a function as input for func"   )
		if not isinstance(__lowerCAmelCase      , (float, int)   ):
				raise ValueError("differentiate() requires a float as input for position"   )
		if not isinstance(__lowerCAmelCase      , __lowerCAmelCase   ):
				raise ValueError("differentiate() requires an int as input for order"   )
		_UpperCAmelCase		:       int								=      Dual(__lowerCAmelCase      , 1   )
		_UpperCAmelCase		:       Optional[int]								=      func(__lowerCAmelCase   )
		if order == 0:
				return result.real
		return result.duals[order - 1] * factorial(__lowerCAmelCase   )


if __name__ == "__main__":
						import doctest

						doctest.testmod()






						def  __lowerCAmelCase (__lowerCAmelCase   ):
								return y**2 * y**4





						print(differentiate(f, 9, 2))



