





__lowerCAmelCase :Tuple     =    range(2, 20 + 1)
__lowerCAmelCase :Optional[int]     =    [10**k for k in range(ks[-1] + 1)]
__lowerCAmelCase :dict[int, dict[int, list[list[int]]]]     =    {}







def    A				(							UpperCAmelCase  ,  UpperCAmelCase  ,  UpperCAmelCase  ,  UpperCAmelCase				):
					_snake_case       :					Dict				       =   sum(a_i[j] for j in range(UpperCAmelCase  ,  len(UpperCAmelCase				)				)				)
					_snake_case       :					int				       =   sum(a_i[j] * base[j] for j in range(min(len(UpperCAmelCase				)  ,  UpperCAmelCase				)				)				)

					_snake_case       :					Tuple				       =   0, 0
					_snake_case       :					List[str]				       =   n - i

					_snake_case       :					Any				       =   memo.get(UpperCAmelCase				)

					if sub_memo is not None:
										_snake_case       :					int				       =   sub_memo.get(UpperCAmelCase				)

										if jumps is not None and len(UpperCAmelCase				) > 0:
															# find and make the largest jump without going over
															_snake_case       :					Optional[int]				       =   -1
															for _k in range(len(UpperCAmelCase				) - 1  ,  -1  ,  -1				):
																				if jumps[_k][2] <= k and jumps[_k][1] <= max_dn:
																									_snake_case       :					Any				       =   _k
																									break

															if max_jump >= 0:
																				_snake_case       :					Any				       =   jumps[max_jump]
																				# since the difference between jumps is cached, add c
																				_snake_case       :					List[Any]				       =   diff + c
																				for j in range(min(UpperCAmelCase  ,  len(UpperCAmelCase				)				)				):
																									_snake_case       :					Tuple				       =   divmod(UpperCAmelCase  ,  10				)
																				if new_c > 0:
																									add(UpperCAmelCase  ,  UpperCAmelCase  ,  UpperCAmelCase				)

										else:
															_snake_case       :					List[Any]				       =   []
					else:
										_snake_case       :					str				       =   {c: []}
										_snake_case       :					Optional[int]				       =   sub_memo

					if dn >= max_dn or c + diff >= base[k]:
										return diff, dn

					if k > ks[0]:
										while True:
															# keep doing smaller jumps
															_snake_case       :					List[Any]				       =   next_term(UpperCAmelCase  ,  k - 1  ,  i + dn  ,  UpperCAmelCase				)
															diff += _diff
															dn += terms_jumped

															if dn >= max_dn or c + diff >= base[k]:
																				break
					else:
										# would be too small a jump, just compute sequential terms instead
										_snake_case       :					Optional[int]				       =   compute(UpperCAmelCase  ,  UpperCAmelCase  ,  i + dn  ,  UpperCAmelCase				)
										diff += _diff
										dn += terms_jumped

					_snake_case       :					Optional[Any]				       =   sub_memo[c]

					# keep jumps sorted by # of terms skipped
					_snake_case       :					str				       =   0
					while j < len(UpperCAmelCase				):
										if jumps[j][1] > dn:
															break
										j += 1

					# cache the jump for this value digitsum(b) and c
					sub_memo[c].insert(UpperCAmelCase  ,  (diff, dn, k)				)
					return (diff, dn)







def    A				(							UpperCAmelCase  ,  UpperCAmelCase  ,  UpperCAmelCase  ,  UpperCAmelCase				):
					if i >= n:
										return 0, i
					if k > len(UpperCAmelCase				):
										a_i.extend([0 for _ in range(k - len(UpperCAmelCase				)				)]				)

					# note: a_i -> b * 10^k + c
					# ds_b -> digitsum(b)
					# ds_c -> digitsum(c)
					_snake_case       :					List[Any]				       =   i
					_snake_case       :					str				       =   0, 0, 0
					for j in range(len(UpperCAmelCase				)				):
										if j >= k:
															ds_b += a_i[j]
										else:
															ds_c += a_i[j]

					while i < n:
										i += 1
										_snake_case       :					Optional[Any]				       =   ds_c + ds_b
										diff += addend
										_snake_case       :					Dict				       =   0
										for j in range(UpperCAmelCase				):
															_snake_case       :					List[str]				       =   a_i[j] + addend
															_snake_case       :					List[str]				       =   divmod(UpperCAmelCase  ,  10				)

															ds_c += a_i[j]

										if addend > 0:
															break

					if addend > 0:
										add(UpperCAmelCase  ,  UpperCAmelCase  ,  UpperCAmelCase				)
					return diff, i - start_i







def    A				(							UpperCAmelCase  ,  UpperCAmelCase  ,  UpperCAmelCase				):
					for j in range(UpperCAmelCase  ,  len(UpperCAmelCase				)				):
										_snake_case       :					Optional[int]				       =   digits[j] + addend
										if s >= 10:
															_snake_case       :					str				       =   divmod(UpperCAmelCase  ,  10				)
															_snake_case       :					Any				       =   addend // 10 + quotient
										else:
															_snake_case       :					str				       =   s
															_snake_case       :					int				       =   addend // 10

										if addend == 0:
															break

					while addend > 0:
										_snake_case       :					Tuple				       =   divmod(UpperCAmelCase  ,  10				)
										digits.append(UpperCAmelCase				)







def    A				(							UpperCAmelCase = 10**15				):
					_snake_case       :					List[str]				       =   [1]
					_snake_case       :					List[Any]				       =   1
					_snake_case       :					Any				       =   0
					while True:
										_snake_case       :					List[Any]				       =   next_term(UpperCAmelCase  ,  20  ,  i + dn  ,  UpperCAmelCase				)
										dn += terms_jumped
										if dn == n - i:
															break

					_snake_case       :					Optional[Any]				       =   0
					for j in range(len(UpperCAmelCase				)				):
										a_n += digits[j] * 10**j
					return a_n


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






import numpy as np

__lowerCAmelCase :Dict     =    [
    ['a', 'b', 'c', 'd', 'e'],
    ['f', 'g', 'h', 'i', 'k'],
    ['l', 'm', 'n', 'o', 'p'],
    ['q', 'r', 's', 't', 'u'],
    ['v', 'w', 'x', 'y', 'z'],
]






class        _a:







		def __init__(    self				)      ->      None:


							'''simple docstring'''

							_snake_case       :					Optional[Any]				       =   np.array(__snake_case				)







		def        lowercase       (    self ,						__snake_case				)      ->      np.ndarray:


							'''simple docstring'''

							_snake_case       , _snake_case       :					List[Any]				       =   np.where(letter == self.SQUARE				)
							_snake_case       :					Any				       =   np.concatenate([indexa + 1, indexa + 1]				)
							return indexes







		def        lowercase       (    self ,						__snake_case ,						__snake_case				)      ->      str:


							'''simple docstring'''

							_snake_case       :					int				       =   self.SQUARE[indexa - 1, indexa - 1]
							return letter







		def        lowercase       (    self ,						__snake_case				)      ->      str:


							'''simple docstring'''

							_snake_case       :					Optional[Any]				       =   message.lower()
							_snake_case       :					List[Any]				       =   message.replace(" " ,						""				)
							_snake_case       :					Any				       =   message.replace("j" ,						"i"				)

							_snake_case       :					Tuple				       =   np.empty((2, len(__snake_case				))				)
							for letter_index in range(len(__snake_case				)				):
												_snake_case       :					Dict				       =   self.letter_to_numbers(message[letter_index]				)

												_snake_case       :					Tuple				       =   numbers[0]
												_snake_case       :					List[Any]				       =   numbers[1]

							_snake_case       :					Any				       =   first_step.reshape(2 * len(__snake_case				)				)
							_snake_case       :					Optional[Any]				       =   ""
							for numbers_index in range(len(__snake_case				)				):
												_snake_case       :					Optional[int]				       =   int(second_step[numbers_index * 2]				)
												_snake_case       :					List[str]				       =   int(second_step[(numbers_index * 2) + 1]				)
												_snake_case       :					Any				       =   self.numbers_to_letter(__snake_case ,						__snake_case				)
												_snake_case       :					Any				       =   encoded_message + letter

							return encoded_message







		def        lowercase       (    self ,						__snake_case				)      ->      str:


							'''simple docstring'''

							_snake_case       :					Union[str, Any]				       =   message.lower()
							message.replace(" " ,						""				)
							_snake_case       :					Tuple				       =   np.empty(2 * len(__snake_case				)				)
							for letter_index in range(len(__snake_case				)				):
												_snake_case       :					Union[str, Any]				       =   self.letter_to_numbers(message[letter_index]				)
												_snake_case       :					Tuple				       =   numbers[0]
												_snake_case       :					Any				       =   numbers[1]

							_snake_case       :					Optional[Any]				       =   first_step.reshape((2, len(__snake_case				))				)
							_snake_case       :					Union[str, Any]				       =   ""
							for numbers_index in range(len(__snake_case				)				):
												_snake_case       :					Dict				       =   int(second_step[0, numbers_index]				)
												_snake_case       :					Optional[Any]				       =   int(second_step[1, numbers_index]				)
												_snake_case       :					Union[str, Any]				       =   self.numbers_to_letter(__snake_case ,						__snake_case				)
												_snake_case       :					str				       =   decoded_message + letter

							return decoded_message