'''simple docstring'''
a=  range(2, 2_0 + 1)
a=  [1_0**k for k in range(ks[-1] + 1)]
a=  {}







def  _UpperCamelCase (     _a	:	int				,     _a	:	Optional[int]				,     _a	:	Optional[int]				,     _a	:	str			):




    """simple docstring"""



    __UpperCamelCase	:	Optional[Any]		    =  sum(a_i[j] for j in range(_a				,     len(_a			)			)			)
    __UpperCamelCase	:	Any		    =  sum(a_i[j] * base[j] for j in range(min(len(_a			)				,     _a			)			)			)

    __UpperCamelCase    ,					__UpperCamelCase	:	Optional[int]		    =  0, 0
    __UpperCamelCase	:	int		    =  n - i

    __UpperCamelCase	:	Optional[int]		    =  memo.get(_a			)

    if sub_memo is not None:
        __UpperCamelCase	:	Optional[Any]		    =  sub_memo.get(_a			)

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

            if max_jump >= 0:
                __UpperCamelCase    ,					__UpperCamelCase    ,					__UpperCamelCase	:	Any		    =  jumps[max_jump]
                # since the difference between jumps is cached, add c
                __UpperCamelCase	:	Dict		    =  diff + c
                for j in range(min(_a				,     len(_a			)			)			):
                    __UpperCamelCase    ,					__UpperCamelCase	:	str		    =  divmod(_a				,     1_0			)
                if new_c > 0:
                    add(_a				,     _a				,     _a			)

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

    __UpperCamelCase	:	Optional[int]		    =  sub_memo[c]

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

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







def  _UpperCamelCase (     _a	:	Any				,     _a	:	List[str]				,     _a	:	str				,     _a	:	Optional[int]			):




    """simple docstring"""



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

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

    while i < n:
        i += 1
        __UpperCamelCase	:	List[str]		    =  ds_c + ds_b
        diff += addend
        __UpperCamelCase	:	Optional[int]		    =  0
        for j in range(_a			):
            __UpperCamelCase	:	str		    =  a_i[j] + addend
            __UpperCamelCase    ,					__UpperCamelCase	:	str		    =  divmod(_a				,     1_0			)

            ds_c += a_i[j]

        if addend > 0:
            break

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







def  _UpperCamelCase (     _a	:	Any				,     _a	:	Optional[int]				,     _a	:	Dict			):




    """simple docstring"""



    for j in range(_a				,     len(_a			)			):
        __UpperCamelCase	:	str		    =  digits[j] + addend
        if s >= 1_0:
            __UpperCamelCase    ,					__UpperCamelCase	:	str		    =  divmod(_a				,     1_0			)
            __UpperCamelCase	:	int		    =  addend // 1_0 + quotient
        else:
            __UpperCamelCase	:	List[Any]		    =  s
            __UpperCamelCase	:	Dict		    =  addend // 1_0

        if addend == 0:
            break

    while addend > 0:
        __UpperCamelCase    ,					__UpperCamelCase	:	List[Any]		    =  divmod(_a				,     1_0			)
        digits.append(_a			)







def  _UpperCamelCase (     _a	:	Tuple = 1_0**1_5			):




    """simple docstring"""



    __UpperCamelCase	:	Tuple		    =  [1]
    __UpperCamelCase	:	Optional[Any]		    =  1
    __UpperCamelCase	:	List[Any]		    =  0
    while True:
        __UpperCamelCase    ,					__UpperCamelCase	:	List[str]		    =  next_term(_a				,     2_0				,     i + dn				,     _a			)
        dn += terms_jumped
        if dn == n - i:
            break

    __UpperCamelCase	:	int		    =  0
    for j in range(len(_a			)			):
        a_n += digits[j] * 1_0**j
    return a_n


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




'''simple docstring'''
from timeit import timeit

a=  {
    '''MALAYALAM''': True,
    '''String''': False,
    '''rotor''': True,
    '''level''': True,
    '''A''': True,
    '''BB''': True,
    '''ABC''': False,
    '''amanaplanacanalpanama''': True,  # "a man a plan a canal panama"
}
# Ensure our test data is valid
assert all((key == key[::-1]) is value for key, value in test_data.items())







def  _UpperCamelCase (     _a	:	str			):




    """simple docstring"""



    __UpperCamelCase	:	int		    =  0
    __UpperCamelCase	:	str		    =  len(_a			) - 1
    while start_i < end_i:
        if s[start_i] == s[end_i]:
            start_i += 1
            end_i -= 1
        else:
            return False
    return True







def  _UpperCamelCase (     _a	:	str			):




    """simple docstring"""



    __UpperCamelCase	:	Optional[Any]		    =  len(_a			) // 2
    __UpperCamelCase	:	Tuple		    =  len(_a			)

    # We need to traverse till half of the length of string
    # as we can get access of the i'th last element from
    # i'th index.
    # eg: [0,1,2,3,4,5] => 4th index can be accessed
    # with the help of 1st index (i==n-i-1)
    # where n is length of string
    return all(s[i] == s[n - i - 1] for i in range(_a			)			)







def  _UpperCamelCase (     _a	:	str			):




    """simple docstring"""



    if len(_a			) <= 2:
        return True
    if s[0] == s[len(_a			) - 1]:
        return is_palindrome_recursive(s[1:-1]			)
    else:
        return False







def  _UpperCamelCase (     _a	:	str			):




    """simple docstring"""



    return s == s[::-1]







def  _UpperCamelCase (     _a	:	str			):




    """simple docstring"""



    __UpperCamelCase	:	int		    =  f"""all({name}(key) is value for key, value in test_data.items())"""
    __UpperCamelCase	:	Union[str, Any]		    =  f"""from __main__ import test_data, {name}"""
    __UpperCamelCase	:	Any		    =  5_0_0_0_0_0
    __UpperCamelCase	:	Tuple		    =  timeit(stmt=_a				,     setup=_a				,     number=_a			)
    print(f"""{name:<35} finished {number:,} runs in {result:.5f} seconds"""			)


if __name__ == "__main__":
  for key, value in test_data.items():
    assert is_palindrome(key) is is_palindrome_recursive(key)
    assert is_palindrome(key) is is_palindrome_slice(key)
    print(F"""{key:21} {value}""")
  print('''a man a plan a canal panama''')

  # finished 500,000 runs in 0.46793 seconds
  benchmark_function('''is_palindrome_slice''')
  # finished 500,000 runs in 0.85234 seconds
  benchmark_function('''is_palindrome''')
  # finished 500,000 runs in 1.32028 seconds
  benchmark_function('''is_palindrome_recursive''')
  # finished 500,000 runs in 2.08679 seconds
  benchmark_function('''is_palindrome_traversal''')



