






'''simple docstring'''







class 		UpperCamelCase__    :




  '''simple docstring'''





  def __init__(      self   ,_lowerCAmelCase   ,_lowerCAmelCase       ):
        lowerCamelCase__         =  name
        lowerCamelCase__         =  val






  def __str__(      self       ):
        return F'''{self.__class__.__name__}({self.name}, {self.val})'''






  def __lt__(      self   ,_lowerCAmelCase       ):
        return self.val < other.val




class 		UpperCamelCase__    :




  '''simple docstring'''





  def __init__(      self   ,_lowerCAmelCase       ):
        lowerCamelCase__         =  {}
        lowerCamelCase__         =  {}
        lowerCamelCase__         =  self.build_heap(__lowerCamelCase       )






  def __getitem__(      self   ,_lowerCAmelCase       ):
        return self.get_value(__lowerCamelCase       )






  def 			UpperCamelCase_					(      self   ,_lowerCAmelCase       ):
        return (idx - 1) // 2






  def 			UpperCamelCase_					(      self   ,_lowerCAmelCase       ):
        return idx * 2 + 1






  def 			UpperCamelCase_					(      self   ,_lowerCAmelCase       ):
        return idx * 2 + 2






  def 			UpperCamelCase_					(      self   ,_lowerCAmelCase       ):
        return self.heap_dict[key]






  def 			UpperCamelCase_					(      self   ,_lowerCAmelCase       ):
        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 			UpperCamelCase_					(      self   ,_lowerCAmelCase   ,_lowerCAmelCase       ):






        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__         =  array[smallest], array[idx]
                    (
                        lowerCamelCase__	
                    )         =  (
                        self.idx_of_element[array[smallest]],
                        self.idx_of_element[array[idx]],
                    )
                    lowerCamelCase__         =  smallest
              else:
                    break






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






  def 			UpperCamelCase_					(      self       ):
        return self.heap[0]






  def 			UpperCamelCase_					(      self       ):
        lowerCamelCase__         =  self.heap[-1], self.heap[0]
        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 			UpperCamelCase_					(      self   ,_lowerCAmelCase       ):
        self.heap.append(__lowerCamelCase       )
        lowerCamelCase__         =  len(self.heap       ) - 1
        lowerCamelCase__         =  node.val
        self.sift_up(len(self.heap       ) - 1       )






  def 			UpperCamelCase_					(      self       ):
        return len(self.heap       ) == 0






  def 			UpperCamelCase_					(      self   ,_lowerCAmelCase   ,_lowerCAmelCase       ):
        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]       )



UpperCamelCase    :      Optional[Any]  			=		Node('R', -1)
UpperCamelCase    :      Dict  			=		Node('B', 6)
UpperCamelCase    :      List[Any]  			=		Node('A', 3)
UpperCamelCase    :      List[Any]  			=		Node('X', 1)
UpperCamelCase    :      Union[str, Any]  			=		Node('E', 4)

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

# Generating Min-Heap from array
UpperCamelCase    :      Any  			=		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 __future__ import annotations

import math
def 						A__			(				__lowerCAmelCase		:			int						):

						if 1 < number < 4:
												# 2 and 3 are primes
												return True
						elif number < 2 or number % 2 == 0 or number % 3 == 0:
												# Negatives, 0, 1, all even numbers, all multiples of 3 are not primes
												return False

						# All primes number are in format of 6k +/- 1
						for i in range(5   ,    int(math.sqrt(__lowerCAmelCase						) + 1						)   ,    6						):
												if number % i == 0 or number % (i + 2) == 0:
																		return False
						return True


UpperCamelCase    :      str  			=		[num for num in range(3, 10_00_01, 2) if not is_prime(num)]
def 						A__			(				__lowerCAmelCase		:			int						):
						if not isinstance(__lowerCAmelCase   ,    __lowerCAmelCase						):
												raise ValueError("""n must be an integer"""						)
						if n <= 0:
												raise ValueError("""n must be >= 0"""						)

						lowerCamelCase__         =  []
						for num in range(len(__lowerCAmelCase						)						):
												lowerCamelCase__         =  0
												while 2 * i * i <= odd_composites[num]:
																		lowerCamelCase__         =  odd_composites[num] - 2 * i * i
																		if is_prime(__lowerCAmelCase						):
																								break
																		i += 1
												else:
																		list_nums.append(odd_composites[num]						)
																		if len(__lowerCAmelCase						) == n:
																								return list_nums

						return []
def 						A__			(				):
						return compute_nums(1						)[0]


if __name__ == "__main__":
							print(F'{solution() = }')

