


'''simple docstring'''




from __future__ import annotations

_lowerCAmelCase  :		Dict		     =	list[tuple[int, int]]

_lowerCAmelCase  :		Any		     =	[
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0],
    [1, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0],
]

_lowerCAmelCase  :		str		     =	([-1, 0], [0, -1], [1, 0], [0, 1])  # up, left, down, right



class  lowerCAmelCase				:



	def __init__(					self ,					snake_case__ ,					snake_case__ ,					snake_case__ ,					snake_case__ ,					snake_case__ ,					snake_case__ ,					):
		lowerCAmelCase					:    Any      							= pos_x
		lowerCAmelCase					:    Optional[int]      							= pos_y
		lowerCAmelCase					:    int      							= (pos_y, pos_x)
		lowerCAmelCase					:    Dict      							= goal_x
		lowerCAmelCase					:    str      							= goal_y
		lowerCAmelCase					:    Optional[Any]      							= g_cost
		lowerCAmelCase					:    Optional[Any]      							= parent
		lowerCAmelCase					:    Union[str, Any]      							= self.calculate_heuristic()



	def 				lowercase     (					self    ):
		lowerCAmelCase					:    Optional[Any]      							= abs(self.pos_x - self.goal_x    )
		lowerCAmelCase					:    Optional[Any]      							= abs(self.pos_y - self.goal_y    )
		return dx + dy



	def __lt__(					self ,					snake_case__    ):
		return self.f_cost < other.f_cost



class  lowerCAmelCase				:



	def __init__(					self ,					snake_case__ ,					snake_case__    ):
		lowerCAmelCase					:    Optional[Any]      							= Node(start[1] ,					start[0] ,					goal[1] ,					goal[0] ,					0 ,					snake_case__    )
		lowerCAmelCase					:    List[str]      							= Node(goal[1] ,					goal[0] ,					goal[1] ,					goal[0] ,					9_9999 ,					snake_case__    )

		lowerCAmelCase					:    List[Any]      							= [self.start]
		lowerCAmelCase					:    list[Node]      							= []

		lowerCAmelCase					:    List[str]      							= False



	def 				lowercase     (					self    ):
		while self.open_nodes:
			# Open Nodes are sorted using __lt__
			self.open_nodes.sort()
			lowerCAmelCase					:    int      							= self.open_nodes.pop(0    )

			if current_node.pos == self.target.pos:
				lowerCAmelCase					:    Optional[Any]      							= True
				return self.retrace_path(snake_case__    )

			self.closed_nodes.append(snake_case__    )
			lowerCAmelCase					:    str      							= self.get_successors(snake_case__    )

			for child_node in successors:
				if child_node in self.closed_nodes:
					continue

				if child_node not in self.open_nodes:
					self.open_nodes.append(snake_case__    )
				else:
					# retrieve the best current path
					lowerCAmelCase					:    Any      							= self.open_nodes.pop(self.open_nodes.index(snake_case__    )    )

					if child_node.g_cost < better_node.g_cost:
						self.open_nodes.append(snake_case__    )
					else:
						self.open_nodes.append(snake_case__    )

		if not self.reached:
			return [self.start.pos]
		return None



	def 				lowercase     (					self ,					snake_case__    ):
		lowerCAmelCase					:    Union[str, Any]      							= []
		for action in delta:
			lowerCAmelCase					:    List[str]      							= parent.pos_x + action[1]
			lowerCAmelCase					:    Optional[int]      							= parent.pos_y + action[0]

			if not (0 <= pos_x <= len(grid[0]    ) - 1 and 0 <= pos_y <= len(snake_case__    ) - 1):
				continue

			if grid[pos_y][pos_x] != 0:
				continue

			successors.append(
			    Node(
			        snake_case__ ,					snake_case__ ,					self.target.pos_y ,					self.target.pos_x ,					parent.g_cost + 1 ,					snake_case__ ,					)    )
		return successors



	def 				lowercase     (					self ,					snake_case__    ):
		lowerCAmelCase					:    List[Any]      							= node
		lowerCAmelCase					:    int      							= []
		while current_node is not None:
			path.append((current_node.pos_y, current_node.pos_x)    )
			lowerCAmelCase					:    Tuple      							= current_node.parent
		path.reverse()
		return path


if __name__ == "__main__":
				_lowerCAmelCase  :		Tuple		     =	(0, 0)
				_lowerCAmelCase  :		Tuple		     =	(len(grid) - 1, len(grid[0]) - 1)
				for elem in grid:
								print(elem)

				print('------')

				_lowerCAmelCase  :		List[str]		     =	GreedyBestFirst(init, goal)
				_lowerCAmelCase  :		Dict		     =	greedy_bf.search()
				if path:
								for pos_x, pos_y in path:
												_lowerCAmelCase  :		List[str]		     =	2

								for elem in grid:
												print(elem)




'''simple docstring'''




import math

def 			__UpperCamelCase    (    _A    :				int = 1_00				)    ->      int:




	"""simple docstring"""





	lowerCAmelCase					:    List[Any]      							= sum(i * i for i in range(1					,   n + 1				)				)
	lowerCAmelCase					:    Optional[Any]      							= int(math.pow(sum(range(1					,   n + 1				)				)					,   2				)				)
	return square_of_sum - sum_of_squares


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