





from heapq import heappop, heappush

import numpy as np





def      _lowercase					(						_UpperCAmelCase			,      _UpperCAmelCase			,      _UpperCAmelCase			,      _UpperCAmelCase			,      )						->  tuple[float | int, list[tuple[int, int]]]:
				lowerCamelCase ,  lowerCamelCase	 =grid.shape
				lowerCamelCase	 =[-1, 1, 0, 0]
				lowerCamelCase	 =[0, 0, -1, 1]
				if allow_diagonal:
								dx += [-1, -1, 1, 1]
								dy += [-1, 1, -1, 1]

				lowerCamelCase ,  lowerCamelCase	 =[(0, source)], set()
				lowerCamelCase	 =np.full((rows, cols)			,      np.inf				)
				lowerCamelCase	 =0
				lowerCamelCase	 =np.empty((rows, cols)			,      dtype=_UpperCAmelCase				)
				lowerCamelCase	 =None

				while queue:
								((lowerCamelCase) ,  (lowerCamelCase))	 =heappop(_UpperCAmelCase				)
								if (x, y) in visited:
												continue
								visited.add((x, y)				)

								if (x, y) == destination:
												lowerCamelCase	 =[]
												while (x, y) != source:
																path.append((x, y)				)
																lowerCamelCase ,  lowerCamelCase	 =predecessors[x, y]
												path.append(_UpperCAmelCase				)  # add the source manually
												path.reverse()
												return matrix[destination], path

								for i in range(len(_UpperCAmelCase				)				):
												lowerCamelCase ,  lowerCamelCase	 =x + dx[i], y + dy[i]
												if 0 <= nx < rows and 0 <= ny < cols:
																lowerCamelCase	 =grid[nx][ny]
																if next_node == 1 and matrix[nx, ny] > dist + 1:
																				heappush(_UpperCAmelCase			,      (dist + 1, (nx, ny))				)
																				lowerCamelCase	 =dist + 1
																				lowerCamelCase	 =(x, y)

				return np.inf, []


if __name__ == "__main__":
							import doctest

							doctest.testmod()












import math
from collections.abc import Iterator
from itertools import takewhile





def      _lowercase					(						_UpperCAmelCase				)						->  bool:

				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(_UpperCAmelCase				) + 1				)			,      6				):
								if number % i == 0 or number % (i + 2) == 0:
												return False
				return True





def      _lowercase					(						)						->  Iterator[int]:
				lowerCamelCase	 =2
				while True:
								if is_prime(_UpperCAmelCase				):
												yield num
								num += 1





def      _lowercase					(						_UpperCAmelCase = 2_00_00_00				)						->  int:
				return sum(takewhile(lambda _UpperCAmelCase				: x < n			,      prime_generator()				)				)


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





