'''simple docstring'''




import math
import sys

class      lowerCamelCase_     :
      '''simple docstring'''

      def __init__(	self						:    Tuple	):
             _UpperCAmelCase					:  List[str]											=   0
             _UpperCAmelCase					:  Optional[Any]											=   []
             _UpperCAmelCase					:  str											=   {}  # To store the pos of node in array




      def 					_A     (	self						:    List[Any]	):
             return self.cur_size == 0




      def 					_A     (	self						:    Any						, A						:    int	):
             _UpperCAmelCase					:  List[Any]											=   self.left(A	)
             _UpperCAmelCase					:  Tuple											=   self.right(A	)
             if lc < self.cur_size and self.array(A	)[0] < self.array(A	)[0]:
                    _UpperCAmelCase					:  Dict											=   lc
             else:
                    _UpperCAmelCase					:  Union[str, Any]											=   idx
             if rc < self.cur_size and self.array(A	)[0] < self.array(A	)[0]:
                    _UpperCAmelCase					:  Optional[Any]											=   rc
             if smallest != idx:
                    self.swap(A						, A	)
                    self.min_heapify(A	)




      def 					_A     (	self						:    int						, A						:    int	):
             # Inserts a node into the Priority Queue
             _UpperCAmelCase					:  Dict											=   self.cur_size
             self.cur_size += 1
             self.array.append((sys.maxsize, tup[1])	)
             self.decrease_key((sys.maxsize, tup[1])						, tup[0]	)




      def 					_A     (	self						:    List[str]	):
             # Removes and returns the min element at top of priority queue
             _UpperCAmelCase					:  int											=   self.array[0][1]
             _UpperCAmelCase					:  Any											=   self.array[self.cur_size - 1]
             self.cur_size -= 1
             self.min_heapify(1	)
             del self.pos[min_node]
             return min_node




      def 					_A     (	self						:    Union[str, Any]						, A						:    Union[str, Any]	):
             # returns the index of left child
             return 2 * i + 1




      def 					_A     (	self						:    Tuple						, A						:    Tuple	):
             # returns the index of right child
             return 2 * i + 2




      def 					_A     (	self						:    List[str]						, A						:    Dict	):
             # returns the index of parent
             return math.floor(i / 2	)




      def 					_A     (	self						:    Union[str, Any]						, A						:    Any						, A						:    Union[str, Any]	):
             # swaps array elements at indices i and j
             # update the pos{}
             _UpperCAmelCase					:  Tuple											=   j
             _UpperCAmelCase					:  Any											=   i
             _UpperCAmelCase					:  List[str]											=   self.array[i]
             _UpperCAmelCase					:  List[Any]											=   self.array[j]
             _UpperCAmelCase					:  List[str]											=   temp





      def 					_A     (	self						:    Tuple						, A						:    Optional[Any]						, A						:    int	):
             _UpperCAmelCase					:  Dict											=   self.pos[tup[1]]
             # assuming the new_d is atmost old_d
             _UpperCAmelCase					:  Any											=   (new_d, tup[1])
             while idx > 0 and self.array[self.par(A	)][0] > self.array[idx][0]:
                    self.swap(A						, self.par(A	)	)
                    _UpperCAmelCase					:  List[str]											=   self.par(A	)

class      lowerCamelCase_     :
      '''simple docstring'''

      def __init__(	self						:    Optional[Any]						, A						:    List[str]	):
             _UpperCAmelCase					:  Optional[Any]											=   {}  # To store graph: u -> (v,w)
             _UpperCAmelCase					:  Union[str, Any]											=   num  # Number of nodes in graph
             # To store the distance from source vertex
             _UpperCAmelCase					:  Tuple											=   [0] * self.num_nodes
             _UpperCAmelCase					:  Any											=   [-1] * self.num_nodes  # To store the path




      def 					_A     (	self						:    str						, A						:    List[Any]						, A						:    int						, A						:    Optional[int]	):
             #  Edge going from node u to v and v to u with weight w
             # u (w)-> v, v (w) -> u
             # Check if u already in graph
             if u in self.adjList:
                    self.adjList[u].append((v, w)	)
             else:
                    _UpperCAmelCase					:  Optional[int]											=   [(v, w)]

             # Assuming undirected graph
             if v in self.adjList:
                    self.adjList[v].append((u, w)	)
             else:
                    _UpperCAmelCase					:  Tuple											=   [(u, w)]




      def 					_A     (	self						:    Any	):
             # u -> v(w)
             for u in self.adjList:
                    print(A						, "->"						, " -> ".join(str(F"""{v}({w})"""	) for v, w in self.adjList[u]	)	)




      def 					_A     (	self						:    str						, A						:    Optional[int]	):
             # Flush old junk values in par[]
             _UpperCAmelCase					:  Tuple											=   [-1] * self.num_nodes
             # src is the source node
             _UpperCAmelCase					:  str											=   0
             _UpperCAmelCase					:  List[str]											=   PriorityQueue()
             q.insert((0, src)	)  # (dist from src, node)
             for u in self.adjList:
                    if u != src:
                           _UpperCAmelCase					:  Dict											=   sys.maxsize  # Infinity
                           _UpperCAmelCase					:  str											=   -1

             while not q.is_empty():
                    _UpperCAmelCase					:  Dict											=   q.extract_min()  # Returns node with the min dist from source
                    # Update the distance of all the neighbours of u and
                    # if their prev dist was INFINITY then push them in Q
                    for v, w in self.adjList[u]:
                           _UpperCAmelCase					:  Tuple											=   self.dist[u] + w
                           if self.dist[v] > new_dist:
                                  if self.dist[v] == sys.maxsize:
                                         q.insert((new_dist, v)	)
                                  else:
                                         q.decrease_key((self.dist[v], v)						, A	)
                                  _UpperCAmelCase					:  Tuple											=   new_dist
                                  _UpperCAmelCase					:  Tuple											=   u

        # Show the shortest distances from src
             self.show_distances(A	)




      def 					_A     (	self						:    List[Any]						, A						:    Union[str, Any]	):
             print(F"""Distance from node: {src}"""	)
             for u in range(self.num_nodes	):
                    print(F"""Node {u} has distance: {self.dist[u]}"""	)





      def 					_A     (	self						:    Any						, A						:    Union[str, Any]						, A						:    List[Any]	):
             # To show the shortest path from src to dest
             # WARNING: Use it *after* calling dijkstra
             _UpperCAmelCase					:  Tuple											=   []
             _UpperCAmelCase					:  Optional[Any]											=   0
             _UpperCAmelCase					:  Dict											=   dest
             # Backtracking from dest to src
             while self.par[temp] != -1:
                    path.append(A	)
                    if temp != src:
                           for v, w in self.adjList[temp]:
                                  if v == self.par[temp]:
                                         cost += w
                                         break
                    _UpperCAmelCase					:  Tuple											=   self.par[temp]
             path.append(A	)
             path.reverse()

             print(F"""----Path to reach {dest} from {src}----"""	)
             for u in path:
                    print(F"""{u}"""						, end=" "	)
                    if u != dest:
                           print("-> "						, end=""	)

             print("\nTotal cost of path: "						, A	)


if __name__ == "__main__":
  __SCREAMING_SNAKE_CASE	:					Optional[Any]					=  Graph(9)
  graph.add_edge(0, 1, 4)
  graph.add_edge(0, 7, 8)
  graph.add_edge(1, 2, 8)
  graph.add_edge(1, 7, 11)
  graph.add_edge(2, 3, 7)
  graph.add_edge(2, 8, 2)
  graph.add_edge(2, 5, 4)
  graph.add_edge(3, 4, 9)
  graph.add_edge(3, 5, 14)
  graph.add_edge(4, 5, 10)
  graph.add_edge(5, 6, 2)
  graph.add_edge(6, 7, 1)
  graph.add_edge(6, 8, 6)
  graph.add_edge(7, 8, 7)
  graph.show_graph()
  graph.dijkstra(0)
  graph.show_path(0, 4)

# OUTPUT
# 0 -> 1(4) -> 7(8)
# 1 -> 0(4) -> 2(8) -> 7(11)
# 7 -> 0(8) -> 1(11) -> 6(1) -> 8(7)
# 2 -> 1(8) -> 3(7) -> 8(2) -> 5(4)
# 3 -> 2(7) -> 4(9) -> 5(14)
# 8 -> 2(2) -> 6(6) -> 7(7)
# 5 -> 2(4) -> 3(14) -> 4(10) -> 6(2)
# 4 -> 3(9) -> 5(10)
# 6 -> 5(2) -> 7(1) -> 8(6)
# Distance from node: 0
# Node 0 has distance: 0
# Node 1 has distance: 4
# Node 2 has distance: 12
# Node 3 has distance: 19
# Node 4 has distance: 21
# Node 5 has distance: 11
# Node 6 has distance: 9
# Node 7 has distance: 8
# Node 8 has distance: 14
# ----Path to reach 4 from 0----
# 0 -> 7 -> 6 -> 5 -> 4
# Total cost of path:  21


'''simple docstring'''




from itertools import compress, repeat
from math import ceil, sqrt

def      UpperCamelCase_							( _UpperCAmelCase  :				int   )   ->   list[int]:


       """simple docstring"""







       if num <= 2:
              return []
       if num == 3:
              return [2]

       # Odd sieve for numbers in range [3, num - 1]
       _UpperCAmelCase					:  Optional[int]											=   bytearray(b"\x01"   ) * ((num >> 1) - 1)

       for i in range(3      ,     int(sqrt(_UpperCAmelCase   )   ) + 1      ,     2   ):
              if sieve[(i >> 1) - 1]:
                     _UpperCAmelCase					:  List[Any]											=   i**2
                     _UpperCAmelCase					:  Optional[int]											=   repeat(
                         0      ,     ceil((num - i_squared) / (i << 1)   )   )

       return [2] + list(compress(range(3      ,     _UpperCAmelCase      ,     2   )      ,     _UpperCAmelCase   )   )


if __name__ == "__main__":
  import doctest

  doctest.testmod()

