




_lowerCAmelCase						:   Any		=   range(2, 2_0 + 1)
_lowerCAmelCase						:   Union[str, Any]		=   [1_0**k for k in range(ks[-1] + 1)]
_lowerCAmelCase						:   Any		=   {}



def 						lowerCAmelCase		(		_lowerCAmelCase							:   int						,							_lowerCAmelCase							:   str						,							_lowerCAmelCase							:   Any						,							_lowerCAmelCase							:   Union[str, Any]	)     ->   Optional[Any]:




 """simple docstring"""







 UpperCAmelCase__							 =						sum(a_i[j] for j in range(lowerCamelCase__						,							len(lowerCamelCase__	)	)	)
 UpperCAmelCase__							 =						sum(a_i[j] * base[j] for j in range(min(len(lowerCamelCase__	)						,							lowerCamelCase__	)	)	)

 UpperCAmelCase__ , UpperCAmelCase__							 =						0, 0
 UpperCAmelCase__							 =						n - i

 UpperCAmelCase__							 =						memo.get(lowerCamelCase__	)

 if sub_memo is not None:
  UpperCAmelCase__							 =						sub_memo.get(lowerCamelCase__	)

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

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

  else:
   UpperCAmelCase__							 =						[]
 else:
  UpperCAmelCase__							 =						{c: []}
  UpperCAmelCase__							 =						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__							 =						next_term(lowerCamelCase__						,							k - 1						,							i + dn						,							lowerCamelCase__	)
   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__							 =						compute(lowerCamelCase__						,							lowerCamelCase__						,							i + dn						,							lowerCamelCase__	)
  diff += _diff
  dn += terms_jumped

 UpperCAmelCase__							 =						sub_memo[c]

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

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



def 						lowerCAmelCase		(		_lowerCAmelCase							:   str						,							_lowerCAmelCase							:   int						,							_lowerCAmelCase							:   Optional[Any]						,							_lowerCAmelCase							:   Union[str, Any]	)     ->   List[str]:




 """simple docstring"""







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

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

 while i < n:
  i += 1
  UpperCAmelCase__							 =						ds_c + ds_b
  diff += addend
  UpperCAmelCase__							 =						0
  for j in range(lowerCamelCase__	):
   UpperCAmelCase__							 =						a_i[j] + addend
   UpperCAmelCase__ , UpperCAmelCase__							 =						divmod(lowerCamelCase__						,							10	)

   ds_c += a_i[j]

  if addend > 0:
   break

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



def 						lowerCAmelCase		(		_lowerCAmelCase							:   Any						,							_lowerCAmelCase							:   Optional[int]						,							_lowerCAmelCase							:   Union[str, Any]	)     ->   int:




 """simple docstring"""







 for j in range(lowerCamelCase__						,							len(lowerCamelCase__	)	):
  UpperCAmelCase__							 =						digits[j] + addend
  if s >= 10:
   UpperCAmelCase__ , UpperCAmelCase__							 =						divmod(lowerCamelCase__						,							10	)
   UpperCAmelCase__							 =						addend // 10 + quotient
  else:
   UpperCAmelCase__							 =						s
   UpperCAmelCase__							 =						addend // 10

  if addend == 0:
   break

 while addend > 0:
  UpperCAmelCase__ , UpperCAmelCase__							 =						divmod(lowerCamelCase__						,							10	)
  digits.append(lowerCamelCase__	)



def 						lowerCAmelCase		(		_lowerCAmelCase							:   int = 10**15	)     ->   int:




 """simple docstring"""







 UpperCAmelCase__							 =						[1]
 UpperCAmelCase__							 =						1
 UpperCAmelCase__							 =						0
 while True:
  UpperCAmelCase__ , UpperCAmelCase__							 =						next_term(lowerCamelCase__						,							20						,							i + dn						,							lowerCamelCase__	)
  dn += terms_jumped
  if dn == n - i:
   break

 UpperCAmelCase__							 =						0
 for j in range(len(lowerCamelCase__	)	):
  a_n += digits[j] * 10**j
 return a_n


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











from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_torch_available, is_vision_available


_lowerCAmelCase						:   Optional[int]		=   {
    "configuration_maskformer": ["MASKFORMER_PRETRAINED_CONFIG_ARCHIVE_MAP", "MaskFormerConfig"],
    "configuration_maskformer_swin": ["MaskFormerSwinConfig"],
}

try:
  if not is_vision_available():
    raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
  pass
else:
  _lowerCAmelCase						:   Optional[int]		=   ["MaskFormerFeatureExtractor"]
  _lowerCAmelCase						:   Dict		=   ["MaskFormerImageProcessor"]


try:
  if not is_torch_available():
    raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
  pass
else:
  _lowerCAmelCase						:   int		=   [
      "MASKFORMER_PRETRAINED_MODEL_ARCHIVE_LIST",
      "MaskFormerForInstanceSegmentation",
      "MaskFormerModel",
      "MaskFormerPreTrainedModel",
  ]
  _lowerCAmelCase						:   List[str]		=   [
      "MaskFormerSwinBackbone",
      "MaskFormerSwinModel",
      "MaskFormerSwinPreTrainedModel",
  ]

if TYPE_CHECKING:
  from .configuration_maskformer import MASKFORMER_PRETRAINED_CONFIG_ARCHIVE_MAP, MaskFormerConfig
  from .configuration_maskformer_swin import MaskFormerSwinConfig

  try:
    if not is_vision_available():
      raise OptionalDependencyNotAvailable()
  except OptionalDependencyNotAvailable:
    pass
  else:
    from .feature_extraction_maskformer import MaskFormerFeatureExtractor
    from .image_processing_maskformer import MaskFormerImageProcessor
  try:
    if not is_torch_available():
      raise OptionalDependencyNotAvailable()
  except OptionalDependencyNotAvailable:
    pass
  else:
    from .modeling_maskformer import (
        MASKFORMER_PRETRAINED_MODEL_ARCHIVE_LIST,
        MaskFormerForInstanceSegmentation,
        MaskFormerModel,
        MaskFormerPreTrainedModel,
    )
    from .modeling_maskformer_swin import (
        MaskFormerSwinBackbone,
        MaskFormerSwinModel,
        MaskFormerSwinPreTrainedModel,
    )


else:
  import sys

  _lowerCAmelCase						:   str		=   _LazyModule(__name__, globals()["__file__"], _import_structure)





