






lowerCamelCase__							=     range(2, 20 + 1)
lowerCamelCase__							=     [10**k for k in range(ks[-1] + 1)]
lowerCamelCase__							=     {}






def   UpperCamelCase  (       snake_case__     :   Dict	,snake_case__     :   Union[str, Any]	,snake_case__     :   List[str]	,snake_case__     :   str  ):




     '''simple docstring'''






     __snake_case			:Optional[int]          =						sum(a_i[j] for j in range(snake_case__	,len(snake_case__  )  )  )
     __snake_case			:Optional[Any]          =						sum(a_i[j] * base[j] for j in range(min(len(snake_case__  )	,snake_case__  )  )  )

     __snake_case       , __snake_case			:List[str]          =						0, 0
     __snake_case			:Optional[int]          =						n - i

     __snake_case			:Optional[int]          =						memo.get(snake_case__  )

     if sub_memo is not None:
          __snake_case			:List[str]          =						sub_memo.get(snake_case__  )

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

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

          else:
               __snake_case			:List[str]          =						[]
     else:
          __snake_case			:int          =						{c: []}
          __snake_case			:List[Any]          =						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       , __snake_case			:Dict          =						next_term(snake_case__	,k - 1	,i + dn	,snake_case__  )
               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       , __snake_case			:Optional[int]          =						compute(snake_case__	,snake_case__	,i + dn	,snake_case__  )
          diff += _diff
          dn += terms_jumped

     __snake_case			:Optional[int]          =						sub_memo[c]

     # keep jumps sorted by # of terms skipped
     __snake_case			:Union[str, Any]          =						0
     while j < len(snake_case__  ):
          if jumps[j][1] > dn:
               break
          j += 1

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






def   UpperCamelCase  (       snake_case__     :   List[Any]	,snake_case__     :   List[Any]	,snake_case__     :   List[str]	,snake_case__     :   Optional[Any]  ):




     '''simple docstring'''






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

     # note: a_i -> b * 10^k + c
     # ds_b -> digitsum(b)
     # ds_c -> digitsum(c)
     __snake_case			:Dict          =						i
     __snake_case       , __snake_case       , __snake_case			:Optional[int]          =						0, 0, 0
     for j in range(len(snake_case__  )  ):
          if j >= k:
               ds_b += a_i[j]
          else:
               ds_c += a_i[j]

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

               ds_c += a_i[j]

          if addend > 0:
               break

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






def   UpperCamelCase  (       snake_case__     :   str	,snake_case__     :   List[str]	,snake_case__     :   str  ):




     '''simple docstring'''






     for j in range(snake_case__	,len(snake_case__  )  ):
          __snake_case			:List[str]          =						digits[j] + addend
          if s >= 10:
               __snake_case       , __snake_case			:Optional[Any]          =						divmod(snake_case__	,10  )
               __snake_case			:Optional[Any]          =						addend // 10 + quotient
          else:
               __snake_case			:Dict          =						s
               __snake_case			:int          =						addend // 10

          if addend == 0:
               break

     while addend > 0:
          __snake_case       , __snake_case			:Optional[Any]          =						divmod(snake_case__	,10  )
          digits.append(snake_case__  )






def   UpperCamelCase  (       snake_case__     :   int = 10**15  ):




     '''simple docstring'''






     __snake_case			:Dict          =						[1]
     __snake_case			:Tuple          =						1
     __snake_case			:Optional[int]          =						0
     while True:
          __snake_case       , __snake_case			:Any          =						next_term(snake_case__	,20	,i + dn	,snake_case__  )
          dn += terms_jumped
          if dn == n - i:
               break

     __snake_case			:List[str]          =						0
     for j in range(len(snake_case__  )  ):
          a_n += digits[j] * 10**j
     return a_n


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










def   UpperCamelCase  (       snake_case__     :   str	,snake_case__     :   int  ):




     '''simple docstring'''






     __snake_case			:list[list[str]]          =						[[] for _ in range(snake_case__  )]
     __snake_case			:Union[str, Any]          =						key - 1

     if key <= 0:
          raise ValueError("""Height of grid can't be 0 or negative"""  )
     if key == 1 or len(snake_case__  ) <= key:
          return input_string

     for position, character in enumerate(snake_case__  ):
          __snake_case			:Any          =						position % (lowest * 2)  # puts it in bounds
          __snake_case			:Optional[int]          =						min(snake_case__	,lowest * 2 - num  )  # creates zigzag pattern
          temp_grid[num].append(snake_case__  )
     __snake_case			:List[Any]          =						["""""".join(snake_case__  ) for row in temp_grid]
     __snake_case			:Any          =						"""""".join(snake_case__  )

     return output_string






def   UpperCamelCase  (       snake_case__     :   str	,snake_case__     :   int  ):




     '''simple docstring'''






     __snake_case			:Union[str, Any]          =						[]
     __snake_case			:Optional[int]          =						key - 1

     if key <= 0:
          raise ValueError("""Height of grid can't be 0 or negative"""  )
     if key == 1:
          return input_string

     __snake_case			:list[list[str]]          =						[[] for _ in range(snake_case__  )]  # generates template
     for position in range(len(snake_case__  )  ):
          __snake_case			:List[str]          =						position % (lowest * 2)  # puts it in bounds
          __snake_case			:int          =						min(snake_case__	,lowest * 2 - num  )  # creates zigzag pattern
          temp_grid[num].append("""*"""  )

     __snake_case			:str          =						0
     for row in temp_grid:  # fills in the characters
          __snake_case			:str          =						input_string[counter : counter + len(snake_case__  )]
          grid.append(list(snake_case__  )  )
          counter += len(snake_case__  )

     __snake_case			:Any          =						""""""  # reads as zigzag
     for position in range(len(snake_case__  )  ):
          __snake_case			:Optional[int]          =						position % (lowest * 2)  # puts it in bounds
          __snake_case			:int          =						min(snake_case__	,lowest * 2 - num  )  # creates zigzag pattern
          output_string += grid[num][0]
          grid[num].pop(0  )
     return output_string






def   UpperCamelCase  (       snake_case__     :   str  ):




     '''simple docstring'''






     __snake_case			:Optional[Any]          =						{}
     for key_guess in range(1	,len(snake_case__  )  ):  # tries every key
          __snake_case			:Dict          =						decrypt(snake_case__	,snake_case__  )
     return results


if __name__ == "__main__":
     import doctest

     doctest.testmod()


