



class 							lowerCAmelCase_						:
       def __init__(     self,     SCREAMING_SNAKE_CASE_,     SCREAMING_SNAKE_CASE_			)	->						List[str]:
          UpperCamelCase       :    List[Any]		      =      name
          UpperCamelCase       :    Tuple		      =      val
       def __str__(     self			)	->						List[str]:
          return F"""{self.__class__.__name__}({self.name}, {self.val})"""






       def __lt__(     self,     SCREAMING_SNAKE_CASE_			)	->						int:
          return self.val < other.val






class 							lowerCAmelCase_						:
       def __init__(     self,     SCREAMING_SNAKE_CASE_			)	->						Optional[int]:
          UpperCamelCase       :    List[Any]		      =      {}
          UpperCamelCase       :    Dict		      =      {}
          UpperCamelCase       :    Optional[int]		      =      self.build_heap(SCREAMING_SNAKE_CASE_			)
       def __getitem__(     self,     SCREAMING_SNAKE_CASE_			)	->						List[str]:
          return self.get_value(SCREAMING_SNAKE_CASE_			)
       def    snake_case_			(     self,     SCREAMING_SNAKE_CASE_			)	->						List[str]:
          return (idx - 1) // 2
       def    snake_case_			(     self,     SCREAMING_SNAKE_CASE_			)	->						Optional[int]:
          return idx * 2 + 1
       def    snake_case_			(     self,     SCREAMING_SNAKE_CASE_			)	->						Optional[Any]:
          return idx * 2 + 2
       def    snake_case_			(     self,     SCREAMING_SNAKE_CASE_			)	->						int:
          return self.heap_dict[key]
       def    snake_case_			(     self,     SCREAMING_SNAKE_CASE_			)	->						Any:
          UpperCamelCase       :    Optional[Any]		      =      len(SCREAMING_SNAKE_CASE_			) - 1
          UpperCamelCase       :    Optional[Any]		      =      self.get_parent_idx(SCREAMING_SNAKE_CASE_			)

          for idx, i in enumerate(SCREAMING_SNAKE_CASE_			):
             UpperCamelCase       :    List[Any]		      =      idx
             UpperCamelCase       :    Dict		      =      i.val

          for i in range(SCREAMING_SNAKE_CASE_,     -1,     -1			):
             self.sift_down(SCREAMING_SNAKE_CASE_,     SCREAMING_SNAKE_CASE_			)
          return array
       def    snake_case_			(     self,     SCREAMING_SNAKE_CASE_,     SCREAMING_SNAKE_CASE_			)	->						Dict:
          while True:
             UpperCamelCase       :    Optional[int]		      =      self.get_left_child_idx(SCREAMING_SNAKE_CASE_			)  # noqa: E741
             UpperCamelCase       :    Union[str, Any]		      =      self.get_right_child_idx(SCREAMING_SNAKE_CASE_			)

             UpperCamelCase       :    Optional[int]		      =      idx
             if l < len(SCREAMING_SNAKE_CASE_			) and array[l] < array[idx]:
                UpperCamelCase       :    Tuple		      =      l
             if r < len(SCREAMING_SNAKE_CASE_			) and array[r] < array[smallest]:
                UpperCamelCase       :    Union[str, Any]		      =      r

             if smallest != idx:
                UpperCamelCase      ,	UpperCamelCase       :    Any		      =      array[smallest], array[idx]
                (
                    (
                    UpperCamelCase
                )      ,	(
                    UpperCamelCase
                )      ,	
                )       :    str		      =      (
                    self.idx_of_element[array[smallest]],
                    self.idx_of_element[array[idx]],
                )
                UpperCamelCase       :    Union[str, Any]		      =      smallest
             else:
                break
       def    snake_case_			(     self,     SCREAMING_SNAKE_CASE_			)	->						str:
          UpperCamelCase       :    Union[str, Any]		      =      self.get_parent_idx(SCREAMING_SNAKE_CASE_			)
          while p >= 0 and self.heap[p] > self.heap[idx]:
             UpperCamelCase      ,	UpperCamelCase       :    int		      =      self.heap[idx], self.heap[p]
             UpperCamelCase      ,	UpperCamelCase       :    Optional[int]		      =      (
                 self.idx_of_element[self.heap[idx]],
                 self.idx_of_element[self.heap[p]],
             )
             UpperCamelCase       :    int		      =      p
             UpperCamelCase       :    Optional[Any]		      =      self.get_parent_idx(SCREAMING_SNAKE_CASE_			)
       def    snake_case_			(     self			)	->						Optional[Any]:
          return self.heap[0]
       def    snake_case_			(     self			)	->						List[str]:
          UpperCamelCase      ,	UpperCamelCase       :    Optional[Any]		      =      self.heap[-1], self.heap[0]
          UpperCamelCase      ,	UpperCamelCase       :    Union[str, Any]		      =      (
              self.idx_of_element[self.heap[-1]],
              self.idx_of_element[self.heap[0]],
          )

          UpperCamelCase       :    Union[str, Any]		      =      self.heap.pop()
          del self.idx_of_element[x]
          self.sift_down(0,     self.heap			)
          return x
       def    snake_case_			(     self,     SCREAMING_SNAKE_CASE_			)	->						Dict:
          self.heap.append(SCREAMING_SNAKE_CASE_			)
          UpperCamelCase       :    Tuple		      =      len(self.heap			) - 1
          UpperCamelCase       :    Dict		      =      node.val
          self.sift_up(len(self.heap			) - 1			)
       def    snake_case_			(     self			)	->						Union[str, Any]:
          return len(self.heap			) == 0






       def    snake_case_			(     self,     SCREAMING_SNAKE_CASE_,     SCREAMING_SNAKE_CASE_			)	->						Tuple:
          assert (
              self.heap[self.idx_of_element[node]].val > new_value
          ), "newValue must be less that current value"
          UpperCamelCase       :    str		      =      new_value
          UpperCamelCase       :    Tuple		      =      new_value
          self.sift_up(self.idx_of_element[node]			)






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

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

# Generating Min-Heap from array
__UpperCAmelCase			  =			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"""




def       a_ (	lowercase__ :str     ):
			__lowerCamelCase          =      [int(lowercase__     ) for i in ip_va_address.split("""."""     ) if i.isdigit()]
			return len(lowercase__     ) == 4 and all(0 <= int(lowercase__     ) <= 254 for octet in octets     )


if __name__ == "__main__":
					__magic_name__						: Tuple    =				input().strip()
					__magic_name__						: Optional[int]    =				'valid' if is_ip_va_address_valid(ip) else 'invalid'
					print(f"""{ip} is a {valid_or_invalid} IP v4 address.""")




