




'''simple docstring'''



import sys

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







def       _UpperCamelCase			(_lowerCamelCase				:  str						)-> int:




     '''simple docstring'''





     __snake_case            =	1
     for digit in s:
          product *= int(_lowerCamelCase						)
     return product







def       _UpperCamelCase			(_lowerCamelCase				:  str = N						)-> int:




     '''simple docstring'''





     __snake_case            =	-sys.maxsize - 1
     __snake_case            =	n[:13]
     __snake_case            =	13
     while cur_index < len(_lowerCamelCase						) - 13:
          if int(n[cur_index]						) >= int(substr[0]						):
               __snake_case            =	substr[1:] + n[cur_index]
               cur_index += 1
          else:
               __snake_case            =	max(_lowerCamelCase ,						str_eval(_lowerCamelCase						)						)
               __snake_case            =	n[cur_index : cur_index + 13]
               cur_index += 13
     return largest_product


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










'''simple docstring'''





class 						a__					:





			'''simple docstring'''

			def __init__(  self							:			Tuple			,    lowerCAmelCase_							:			Optional[Any]			,    lowerCAmelCase_							:			Dict	)      ->		List[str]:
						__A=	name
						__A=	val
			def __str__(  self							:			int	)      ->		List[Any]:
						return F"""{self.__class__.__name__}({self.name}, {self.val})"""

			def __lt__(  self							:			Optional[Any]			,    lowerCAmelCase_							:			str	)      ->		List[Any]:
						return self.val < other.val


class 						a__					:





			'''simple docstring'''

			def __init__(  self							:			Tuple			,    lowerCAmelCase_							:			int	)      ->		Any:
						__A=	{}
						__A=	{}
						__A=	self.build_heap(lowerCAmelCase_	)
			def __getitem__(  self							:			int			,    lowerCAmelCase_							:			Dict	)      ->		Tuple:
						return self.get_value(lowerCAmelCase_	)
			def 					lowerCAmelCase     (  self							:			Tuple			,    lowerCAmelCase_							:			List[str]	)      ->		List[str]:
						return (idx - 1) // 2
			def 					lowerCAmelCase     (  self							:			Union[str, Any]			,    lowerCAmelCase_							:			Union[str, Any]	)      ->		List[str]:
						return idx * 2 + 1
			def 					lowerCAmelCase     (  self							:			Optional[Any]			,    lowerCAmelCase_							:			Union[str, Any]	)      ->		Any:
						return idx * 2 + 2
			def 					lowerCAmelCase     (  self							:			str			,    lowerCAmelCase_							:			Union[str, Any]	)      ->		Dict:
						return self.heap_dict[key]
			def 					lowerCAmelCase     (  self							:			List[Any]			,    lowerCAmelCase_							:			List[Any]	)      ->		Tuple:
						__A=	len(lowerCAmelCase_	) - 1
						__A=	self.get_parent_idx(lowerCAmelCase_	)

						for idx, i in enumerate(lowerCAmelCase_	):
									__A=	idx
									__A=	i.val

						for i in range(lowerCAmelCase_			,    -1			,    -1	):
									self.sift_down(lowerCAmelCase_			,    lowerCAmelCase_	)
						return array
			def 					lowerCAmelCase     (  self							:			int			,    lowerCAmelCase_							:			List[Any]			,    lowerCAmelCase_							:			Tuple	)      ->		Dict:
						while True:
									__A=	self.get_left_child_idx(lowerCAmelCase_	)  # noqa: E741
									__A=	self.get_right_child_idx(lowerCAmelCase_	)

									__A=	idx
									if l < len(lowerCAmelCase_	) and array[l] < array[idx]:
												__A=	l
									if r < len(lowerCAmelCase_	) and array[r] < array[smallest]:
												__A=	r

									if smallest != idx:
												__A,	__A=	array[smallest], array[idx]
												(
												    (
												    __A
												),	(
												    __A
												),	
												)=	(
												    self.idx_of_element[array[smallest]],
												    self.idx_of_element[array[idx]],
												)
												__A=	smallest
									else:
												break
			def 					lowerCAmelCase     (  self							:			Dict			,    lowerCAmelCase_							:			Dict	)      ->		str:
						__A=	self.get_parent_idx(lowerCAmelCase_	)
						while p >= 0 and self.heap[p] > self.heap[idx]:
									__A,	__A=	self.heap[idx], self.heap[p]
									__A,	__A=	(
									    self.idx_of_element[self.heap[idx]],
									    self.idx_of_element[self.heap[p]],
									)
									__A=	p
									__A=	self.get_parent_idx(lowerCAmelCase_	)
			def 					lowerCAmelCase     (  self							:			Optional[Any]	)      ->		Tuple:
						return self.heap[0]
			def 					lowerCAmelCase     (  self							:			List[Any]	)      ->		int:
						__A,	__A=	self.heap[-1], self.heap[0]
						__A,	__A=	(
						    self.idx_of_element[self.heap[-1]],
						    self.idx_of_element[self.heap[0]],
						)

						__A=	self.heap.pop()
						del self.idx_of_element[x]
						self.sift_down(0			,    self.heap	)
						return x
			def 					lowerCAmelCase     (  self							:			Optional[int]			,    lowerCAmelCase_							:			Union[str, Any]	)      ->		Optional[int]:
						self.heap.append(lowerCAmelCase_	)
						__A=	len(self.heap	) - 1
						__A=	node.val
						self.sift_up(len(self.heap	) - 1	)
			def 					lowerCAmelCase     (  self							:			Optional[Any]	)      ->		Tuple:
						return len(self.heap	) == 0

			def 					lowerCAmelCase     (  self							:			Optional[int]			,    lowerCAmelCase_							:			List[Any]			,    lowerCAmelCase_							:			List[Any]	)      ->		Optional[Any]:
						assert (
						    self.heap[self.idx_of_element[node]].val > new_value
						), "newValue must be less that current value"
						__A=	new_value
						__A=	new_value
						self.sift_up(self.idx_of_element[node]	)


UpperCAmelCase__  			=				Node('''R''', -1)
UpperCAmelCase__  			=				Node('''B''', 6)
UpperCAmelCase__  			=				Node('''A''', 3)
UpperCAmelCase__  			=				Node('''X''', 1)
UpperCAmelCase__  			=				Node('''E''', 4)

# Use one of these two ways to generate Min-Heap

# Generating Min-Heap from array
UpperCAmelCase__  			=				MinHeap([r, b, a, x, e])

# Generating Min-Heap by Insert method
# myMinHeap.insert(a)
# myMinHeap.insert(b)
# myMinHeap.insert(x)
# myMinHeap.insert(r)
# myMinHeap.insert(e)

# Before
print('''Min Heap - before decrease key''')
for i in my_min_heap.heap:
					print(i)

print('''Min Heap - After decrease key of node [B -> -17]''')
my_min_heap.decrease_key(b, -1_7)

# After
for i in my_min_heap.heap:
					print(i)

if __name__ == "__main__":
					import doctest

					doctest.testmod()



