






from heapq import heappop, heappush

import numpy as np







def 	_UpperCamelCase   (    UpperCamelCase_       :					np.ndarray    ,       UpperCamelCase_       :					tuple[int, int]    ,       UpperCamelCase_       :					tuple[int, int]    ,       UpperCamelCase_       :					bool    ,       )  ->   tuple[float | int, list[tuple[int, int]]]:

						"""simple docstring"""



						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()













from __future__ import annotations

from functools import lru_cache
from math import ceil

__snake_case    :    Union[str, Any]         =     1_00

__snake_case    :    Tuple         =     set(range(3, NUM_PRIMES, 2))
primes.add(2)
__snake_case    :    int

for prime in range(3, ceil(NUM_PRIMES**0.5), 2):
					if prime not in primes:
										continue
					primes.difference_update(set(range(prime * prime, NUM_PRIMES, prime)))







@lru_cache(maxsize=100		)
def 	_UpperCamelCase   (    UpperCamelCase_       :					int		)  ->   set[int]:

						"""simple docstring"""



						if number_to_partition < 0:
												return set()
						elif number_to_partition == 0:
												return {1}

						lowerCAmelCase__    						=						set()
						lowerCAmelCase__    						=						42
						lowerCAmelCase__    						=						42

						for prime in primes:
												if prime > number_to_partition:
																		continue
												for sub in partition(number_to_partition - prime		):
																		ret.add(sub * prime		)

						return ret







def 	_UpperCamelCase   (    UpperCamelCase_       :					int = 5000		)  ->   int | None:

						"""simple docstring"""



						for number_to_partition in range(1    ,       UpperCamelCase_		):
												if len(partition(UpperCamelCase_		)		) > number_unique_partitions:
																		return number_to_partition
						return None


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





