




import sys

UpperCamelCase								=	(
    '73167176531330624919225119674426574742355349194934'
    '96983520312774506326239578318016984801869478851843'
    '85861560789112949495459501737958331952853208805511'
    '12540698747158523863050715693290963295227443043557'
    '66896648950445244523161731856403098711121722383113'
    '62229893423380308135336276614282806444486645238749'
    '30358907296290491560440772390713810515859307960866'
    '70172427121883998797908792274921901699720888093776'
    '65727333001053367881220235421809751254540594752243'
    '52584907711670556013604839586446706324415722155397'
    '53697817977846174064955149290862569321978468622482'
    '83972241375657056057490261407972968652414535100474'
    '82166370484403199890008895243450658541227588666881'
    '16427171479924442928230863465674813919123162824586'
    '17866458359124566529476545682848912883142607690042'
    '24219022671055626321111109370544217506941658960408'
    '07198403850962455444362981230987879927244284909188'
    '84580156166097919133875499200524063689912560717606'
    '05886116467109405077541002256983155200055935729725'
    '71636269561882670428252483600823257530420752963450'
)



def 				_A  (		lowerCAmelCase_	:   str = N     ):
     """simple docstring"""

     lowerCAmelCase__            =					-sys.maxsize - 1
     for i in range(len(lowerCAmelCase_     ) - 12     ):
          lowerCAmelCase__            =					1
          for j in range(13     ):
               product *= int(n[i + j]     )
          if product > largest_product:
               lowerCAmelCase__            =					product
     return largest_product


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


from __future__ import annotations

import time

lowerCamelCase_    :			Union[str, Any]    =	list[tuple[int, int]]

lowerCamelCase_    :			str    =	[
    [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_    :			Dict    =	[[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right

class 							_UpperCamelCase					:






			'''simple docstring'''

			def __init__(							self			:							Dict    ,						snake_case_			:							int    ,						snake_case_			:							int    ,						snake_case_			:							int    ,						snake_case_			:							int    ,						snake_case_			:							Node | None   ):
							UpperCamelCase_:				str						=    pos_x
							UpperCamelCase_:				List[str]						=    pos_y
							UpperCamelCase_:				str						=    (pos_y, pos_x)
							UpperCamelCase_:				Any						=    goal_x
							UpperCamelCase_:				Optional[int]						=    goal_y
							UpperCamelCase_:				Union[str, Any]						=    parent




class 							_UpperCamelCase					:






			'''simple docstring'''

			def __init__(							self			:							str    ,						snake_case_			:							tuple[int, int]    ,						snake_case_			:							tuple[int, int]   ):
							UpperCamelCase_:				Optional[Any]						=    Node(start[1]    ,						start[0]    ,						goal[1]    ,						goal[0]    ,						snake_case_   )
							UpperCamelCase_:				List[str]						=    Node(goal[1]    ,						goal[0]    ,						goal[1]    ,						goal[0]    ,						snake_case_   )

							UpperCamelCase_:				Any						=    [self.start]
							UpperCamelCase_:				Dict						=    False

			def    lowerCAmelCase__						(							self			:							str   ):
							while self.node_queue:
											UpperCamelCase_:				int						=    self.node_queue.pop(0   )

											if current_node.pos == self.target.pos:
															UpperCamelCase_:				List[str]						=    True
															return self.retrace_path(snake_case_   )

											UpperCamelCase_:				List[str]						=    self.get_successors(snake_case_   )

											for node in successors:
															self.node_queue.append(snake_case_   )

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

			def    lowerCAmelCase__						(							self			:							Dict    ,						snake_case_			:							Node   ):
							UpperCamelCase_:				int						=    []
							for action in delta:
											UpperCamelCase_:				Union[str, Any]						=    parent.pos_x + action[1]
											UpperCamelCase_:				str						=    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    ,						snake_case_   )   )
							return successors




			def    lowerCAmelCase__						(							self			:							int    ,						snake_case_			:							Node | None   ):
							UpperCamelCase_:				int						=    node
							UpperCamelCase_:				Tuple						=    []
							while current_node is not None:
											path.append((current_node.pos_y, current_node.pos_x)   )
											UpperCamelCase_:				List[Any]						=    current_node.parent
							path.reverse()
							return path




class 							_UpperCamelCase					:






			'''simple docstring'''

			def __init__(							self			:							Optional[Any]    ,						snake_case_			:							Optional[Any]    ,						snake_case_			:							Optional[Any]   ):
							UpperCamelCase_:				Tuple						=    BreadthFirstSearch(snake_case_    ,						snake_case_   )
							UpperCamelCase_:				Dict						=    BreadthFirstSearch(snake_case_    ,						snake_case_   )
							UpperCamelCase_:				int						=    False

			def    lowerCAmelCase__						(							self			:							int   ):
							while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
											UpperCamelCase_:				List[Any]						=    self.fwd_bfs.node_queue.pop(0   )
											UpperCamelCase_:				Optional[Any]						=    self.bwd_bfs.node_queue.pop(0   )

											if current_bwd_node.pos == current_fwd_node.pos:
															UpperCamelCase_:				List[Any]						=    True
															return self.retrace_bidirectional_path(
															    snake_case_    ,						snake_case_   )

											UpperCamelCase_:				Optional[Any]						=    current_bwd_node
											UpperCamelCase_:				List[Any]						=    current_fwd_node

											UpperCamelCase_:				List[str]						=    {
											    self.fwd_bfs: self.fwd_bfs.get_successors(snake_case_   ),
											    self.bwd_bfs: self.bwd_bfs.get_successors(snake_case_   ),
											}

											for bfs in [self.fwd_bfs, self.bwd_bfs]:
															for node in successors[bfs]:
																			bfs.node_queue.append(snake_case_   )

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




			def    lowerCAmelCase__						(							self			:							List[str]    ,						snake_case_			:							Node    ,						snake_case_			:							Node   ):
							UpperCamelCase_:				List[str]						=    self.fwd_bfs.retrace_path(snake_case_   )
							UpperCamelCase_:				Tuple						=    self.bwd_bfs.retrace_path(snake_case_   )
							bwd_path.pop()
							bwd_path.reverse()
							UpperCamelCase_:				List[str]						=    fwd_path + bwd_path
							return path


if __name__ == "__main__":
							# all coordinates are given in format [y,x]
							import doctest

							doctest.testmod()
							lowerCamelCase_    :			Tuple    =	(0, 0)
							lowerCamelCase_    :			Union[str, Any]    =	(len(grid) - 1, len(grid[0]) - 1)
							for elem in grid:
														print(elem)

							lowerCamelCase_    :			Optional[int]    =	time.time()
							lowerCamelCase_    :			Tuple    =	BreadthFirstSearch(init, goal)
							lowerCamelCase_    :			List[str]    =	bfs.search()
							lowerCamelCase_    :			Optional[int]    =	time.time() - start_bfs_time

							print("""Unidirectional BFS computation time : """, bfs_time)

							lowerCamelCase_    :			Optional[int]    =	time.time()
							lowerCamelCase_    :			Optional[int]    =	BidirectionalBreadthFirstSearch(init, goal)
							lowerCamelCase_    :			str    =	bd_bfs.search()
							lowerCamelCase_    :			Tuple    =	time.time() - start_bd_bfs_time

							print("""Bidirectional BFS computation time : """, bd_bfs_time)






