






'''simple docstring'''





from collections.abc import Generator
from math import sin






def    lowerCamelCase_     (    lowercase__):
 if len(lowercase__) != 32:
  raise ValueError("Input must be of length 32")

 lowerCamelCase__  =     B""
 for i in [3, 2, 1, 0]:
  little_endian += string_aa[8 * i : 8 * i + 8]
 return little_endian






def    lowerCamelCase_     (    lowercase__):
 if i < 0:
  raise ValueError("Input must be non-negative")

 lowerCamelCase__  =     format(lowercase__				,     "08x")[-8:]
 lowerCamelCase__  =     B""
 for i in [3, 2, 1, 0]:
  little_endian_hex += hex_rep[2 * i : 2 * i + 2].encode("utf-8")
 return little_endian_hex






def    lowerCamelCase_     (    lowercase__):
 lowerCamelCase__  =     B""
 for char in message:
  bit_string += format(lowercase__				,     "08b").encode("utf-8")
 lowerCamelCase__  =     format(len(lowercase__)				,     "064b").encode("utf-8")

 # Pad bit_string to a multiple of 512 chars
 bit_string += b"1"
 while len(lowercase__) % 512 != 448:
  bit_string += b"0"
 bit_string += to_little_endian(start_len[32:]) + to_little_endian(start_len[:32])

 return bit_string






def    lowerCamelCase_     (    lowercase__):
 if len(lowercase__) % 512 != 0:
  raise ValueError("Input must have length that's a multiple of 512")

 for pos in range(0				,     len(lowercase__)				,     512):
  lowerCamelCase__  =     bit_string[pos : pos + 512]
  lowerCamelCase__  =     []
  for i in range(0				,     512				,     32):
   block_words.append(int(to_little_endian(block[i : i + 32])				,     2))
  yield block_words






def    lowerCamelCase_     (    lowercase__):
 if i < 0:
  raise ValueError("Input must be non-negative")

 lowerCamelCase__  =     format(lowercase__				,     "032b")
 lowerCamelCase__  =     ""
 for c in i_str:
  new_str += "1" if c == "0" else "0"
 return int(lowercase__				,     2)






def    lowerCamelCase_     (    lowercase__				,     lowercase__):
 return (a + b) % 2**32






def    lowerCamelCase_     (    lowercase__				,     lowercase__):
 if i < 0:
  raise ValueError("Input must be non-negative")
 if shift < 0:
  raise ValueError("Shift must be non-negative")
 return ((i << shift) ^ (i >> (32 - shift))) % 2**32






def    lowerCamelCase_     (    lowercase__):
 lowerCamelCase__  =     preprocess(lowercase__)

 lowerCamelCase__  =     [int(2**32 * abs(sin(i + 1))) for i in range(64)]

 # Starting states
 lowerCamelCase__  =     0X67_45_23_01
 lowerCamelCase__  =     0XEF_CD_AB_89
 lowerCamelCase__  =     0X98_BA_DC_FE
 lowerCamelCase__  =     0X10_32_54_76

 lowerCamelCase__  =     [
     7,
     12,
     17,
     22,
     7,
     12,
     17,
     22,
     7,
     12,
     17,
     22,
     7,
     12,
     17,
     22,
     5,
     9,
     14,
     20,
     5,
     9,
     14,
     20,
     5,
     9,
     14,
     20,
     5,
     9,
     14,
     20,
     4,
     11,
     16,
     23,
     4,
     11,
     16,
     23,
     4,
     11,
     16,
     23,
     4,
     11,
     16,
     23,
     6,
     10,
     15,
     21,
     6,
     10,
     15,
     21,
     6,
     10,
     15,
     21,
     6,
     10,
     15,
     21,
 ]

 # Process bit string in chunks, each with 16 32-char words
 for block_words in get_block_words(lowercase__):
  lowerCamelCase__  =     aa
  lowerCamelCase__  =     ba
  lowerCamelCase__  =     ca
  lowerCamelCase__  =     da

  # Hash current chunk
  for i in range(64):
   if i <= 15:
    # f = (b & c) | (not_32(b) & d)     # Alternate definition for f
    lowerCamelCase__  =     d ^ (b & (c ^ d))
    lowerCamelCase__  =     i
   elif i <= 31:
    # f = (d & b) | (not_32(d) & c)     # Alternate definition for f
    lowerCamelCase__  =     c ^ (d & (b ^ c))
    lowerCamelCase__  =     (5 * i + 1) % 16
   elif i <= 47:
    lowerCamelCase__  =     b ^ c ^ d
    lowerCamelCase__  =     (3 * i + 5) % 16
   else:
    lowerCamelCase__  =     c ^ (b | not_aa(lowercase__))
    lowerCamelCase__  =     (7 * i) % 16
   lowerCamelCase__  =     (f + a + added_consts[i] + block_words[g]) % 2**32
   lowerCamelCase__  =     d
   lowerCamelCase__  =     c
   lowerCamelCase__  =     b
   lowerCamelCase__  =     sum_aa(lowercase__				,     left_rotate_aa(lowercase__				,     shift_amounts[i]))

  # Add hashed chunk to running total
  lowerCamelCase__  =     sum_aa(lowercase__				,     lowercase__)
  lowerCamelCase__  =     sum_aa(lowercase__				,     lowercase__)
  lowerCamelCase__  =     sum_aa(lowercase__				,     lowercase__)
  lowerCamelCase__  =     sum_aa(lowercase__				,     lowercase__)

 lowerCamelCase__  =     reformat_hex(lowercase__) + reformat_hex(lowercase__) + reformat_hex(lowercase__) + reformat_hex(lowercase__)
 return digest


if __name__ == "__main__":
 import doctest

 doctest.testmod()









'''simple docstring'''





class 				lowercase       :


    '''simple docstring'''

    def __init__(					self     :     Any				,     __lowerCamelCase     :     Union[str, Any]				,     __lowerCamelCase     :     Optional[int]     )							->							Optional[int]:

     '''simple docstring'''




     lowerCamelCase__  =     name
     lowerCamelCase__  =     val

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

     '''simple docstring'''




     return f'''{self.__class__.__name__}({self.name}, {self.val})'''




    def __lt__(					self     :     List[str]				,     __lowerCamelCase     :     List[str]     )							->							str:

     '''simple docstring'''




     return self.val < other.val
class 				lowercase       :


    '''simple docstring'''

    def __init__(					self     :     int				,     __lowerCamelCase     :     Optional[Any]     )							->							List[Any]:

     '''simple docstring'''




     lowerCamelCase__  =     {}
     lowerCamelCase__  =     {}
     lowerCamelCase__  =     self.build_heap(__lowerCamelCase     )

    def __getitem__(					self     :     Tuple				,     __lowerCamelCase     :     Optional[int]     )							->							Tuple:

     '''simple docstring'''




     return self.get_value(__lowerCamelCase     )

    def    a__				(					self     :     str				,     __lowerCamelCase     :     int     )							->							Optional[Any]:

     '''simple docstring'''




     return (idx - 1) // 2

    def    a__				(					self     :     List[str]				,     __lowerCamelCase     :     List[Any]     )							->							Optional[int]:

     '''simple docstring'''




     return idx * 2 + 1

    def    a__				(					self     :     Any				,     __lowerCamelCase     :     str     )							->							Tuple:

     '''simple docstring'''




     return idx * 2 + 2

    def    a__				(					self     :     Any				,     __lowerCamelCase     :     int     )							->							Dict:

     '''simple docstring'''




     return self.heap_dict[key]

    def    a__				(					self     :     str				,     __lowerCamelCase     :     List[str]     )							->							str:

     '''simple docstring'''




     lowerCamelCase__  =     len(__lowerCamelCase     ) - 1
     lowerCamelCase__  =     self.get_parent_idx(__lowerCamelCase     )

     for idx, i in enumerate(__lowerCamelCase     ):
      lowerCamelCase__  =     idx
      lowerCamelCase__  =     i.val

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

    def    a__				(					self     :     List[Any]				,     __lowerCamelCase     :     Tuple				,     __lowerCamelCase     :     Optional[int]     )							->							int:

     '''simple docstring'''




     while True:
      lowerCamelCase__  =     self.get_left_child_idx(__lowerCamelCase     )  # noqa: E741
      lowerCamelCase__  =     self.get_right_child_idx(__lowerCamelCase     )

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

      if smallest != idx:
       lowerCamelCase__  ,	lowerCamelCase__  =     array[smallest], array[idx]
       (
           (
           lowerCamelCase__
       )  ,	(
           lowerCamelCase__
       )  ,	
       )  =     (
           self.idx_of_element[array[smallest]],
           self.idx_of_element[array[idx]],
       )
       lowerCamelCase__  =     smallest
      else:
       break

    def    a__				(					self     :     str				,     __lowerCamelCase     :     Optional[int]     )							->							Union[str, Any]:

     '''simple docstring'''




     lowerCamelCase__  =     self.get_parent_idx(__lowerCamelCase     )
     while p >= 0 and self.heap[p] > self.heap[idx]:
      lowerCamelCase__  ,	lowerCamelCase__  =     self.heap[idx], self.heap[p]
      lowerCamelCase__  ,	lowerCamelCase__  =     (
          self.idx_of_element[self.heap[idx]],
          self.idx_of_element[self.heap[p]],
      )
      lowerCamelCase__  =     p
      lowerCamelCase__  =     self.get_parent_idx(__lowerCamelCase     )

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

     '''simple docstring'''




     return self.heap[0]

    def    a__				(					self     :     Tuple     )							->							int:

     '''simple docstring'''




     lowerCamelCase__  ,	lowerCamelCase__  =     self.heap[-1], self.heap[0]
     lowerCamelCase__  ,	lowerCamelCase__  =     (
         self.idx_of_element[self.heap[-1]],
         self.idx_of_element[self.heap[0]],
     )

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

    def    a__				(					self     :     List[str]				,     __lowerCamelCase     :     Tuple     )							->							List[Any]:

     '''simple docstring'''




     self.heap.append(__lowerCamelCase     )
     lowerCamelCase__  =     len(self.heap     ) - 1
     lowerCamelCase__  =     node.val
     self.sift_up(len(self.heap     ) - 1     )

    def    a__				(					self     :     Dict     )							->							Any:

     '''simple docstring'''




     return len(self.heap     ) == 0




    def    a__				(					self     :     Dict				,     __lowerCamelCase     :     str				,     __lowerCamelCase     :     Union[str, Any]     )							->							Tuple:

     '''simple docstring'''




     assert (
         self.heap[self.idx_of_element[node]].val > new_value
     ), "newValue must be less that current value"
     lowerCamelCase__  =     new_value
     lowerCamelCase__  =     new_value
     self.sift_up(self.idx_of_element[node]     )
__A							:							str  							=		Node("""R""", -1)
__A							:							Dict  							=		Node("""B""", 6)
__A							:							Tuple  							=		Node("""A""", 3)
__A							:							str  							=		Node("""X""", 1)
__A							:							Optional[Any]  							=		Node("""E""", 4)

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

# Generating Min-Heap from array
__A							:							Tuple  							=		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()

