



snake_case_			:     Any  	=  range(2, 20 + 1)
snake_case_			:     Union[str, Any]  	=  [10**k for k in range(ks[-1] + 1)]
snake_case_			:     dict[int, dict[int, list[list[int]]]]  	=  {}






def A__   (					UpperCAmelCase_  ,  UpperCAmelCase_  ,  UpperCAmelCase_  ,  UpperCAmelCase_							):
						_UpperCamelCase :		Optional[int]			    =       sum(a_i[j] for j in range(UpperCAmelCase_  ,  len(UpperCAmelCase_							)							)							)
						_UpperCamelCase :		Tuple			    =       sum(a_i[j] * base[j] for j in range(min(len(UpperCAmelCase_							)  ,  UpperCAmelCase_							)							)							)

						_UpperCamelCase :		Union[str, Any]			    =       0, 0
						_UpperCamelCase :		List[str]			    =       n - i

						_UpperCamelCase :		List[Any]			    =       memo.get(UpperCAmelCase_							)

						if sub_memo is not None:
												_UpperCamelCase :		List[Any]			    =       sub_memo.get(UpperCAmelCase_							)

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

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

												else:
																		_UpperCamelCase :		List[Any]			    =       []
						else:
												_UpperCamelCase :		Any			    =       {c: []}
												_UpperCamelCase :		str			    =       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 :		List[str]			    =       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
												_UpperCamelCase :		Optional[Any]			    =       compute(UpperCAmelCase_  ,  UpperCAmelCase_  ,  i + dn  ,  UpperCAmelCase_							)
												diff += _diff
												dn += terms_jumped

						_UpperCamelCase :		List[str]			    =       sub_memo[c]

						# keep jumps sorted by # of terms skipped
						_UpperCamelCase :		Union[str, Any]			    =       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)
						_UpperCamelCase :		Tuple			    =       i
						_UpperCamelCase :		Any			    =       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
												_UpperCamelCase :		List[Any]			    =       ds_c + ds_b
												diff += addend
												_UpperCamelCase :		Any			    =       0
												for j in range(UpperCAmelCase_							):
																		_UpperCamelCase :		int			    =       a_i[j] + addend
																		_UpperCamelCase :		List[Any]			    =       divmod(UpperCAmelCase_  ,  1_0							)

																		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_							)							):
												_UpperCamelCase :		Dict			    =       digits[j] + addend
												if s >= 1_0:
																		_UpperCamelCase :		Any			    =       divmod(UpperCAmelCase_  ,  1_0							)
																		_UpperCamelCase :		int			    =       addend // 1_0 + quotient
												else:
																		_UpperCamelCase :		int			    =       s
																		_UpperCamelCase :		int			    =       addend // 1_0

												if addend == 0:
																		break

						while addend > 0:
												_UpperCamelCase :		Optional[Any]			    =       divmod(UpperCAmelCase_  ,  1_0							)
												digits.append(UpperCAmelCase_							)






def A__   (					UpperCAmelCase_ = 1_0**1_5							):
						_UpperCamelCase :		Dict			    =       [1]
						_UpperCamelCase :		int			    =       1
						_UpperCamelCase :		int			    =       0
						while True:
												_UpperCamelCase :		Any			    =       next_term(UpperCAmelCase_  ,  2_0  ,  i + dn  ,  UpperCAmelCase_							)
												dn += terms_jumped
												if dn == n - i:
																		break

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


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







'''simple docstring'''
from typing import TYPE_CHECKING

from ...utils import (
    OptionalDependencyNotAvailable,
    _LazyModule,
    is_flax_available,
    is_tf_available,
    is_tokenizers_available,
    is_torch_available,
    is_vision_available,
)


snake_case_			:     Optional[Any]  	=  {
    'configuration_clip': [
        'CLIP_PRETRAINED_CONFIG_ARCHIVE_MAP',
        'CLIPConfig',
        'CLIPOnnxConfig',
        'CLIPTextConfig',
        'CLIPVisionConfig',
    ],
    'processing_clip': ['CLIPProcessor'],
    'tokenization_clip': ['CLIPTokenizer'],
}

try:
					if not is_tokenizers_available():
										raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
					pass
else:
					snake_case_			:     Optional[int]  	=  ['CLIPTokenizerFast']

try:
					if not is_vision_available():
										raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
					pass
else:
					snake_case_			:     Optional[int]  	=  ['CLIPFeatureExtractor']
					snake_case_			:     Dict  	=  ['CLIPImageProcessor']

try:
					if not is_torch_available():
										raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
					pass
else:
					snake_case_			:     Tuple  	=  [
					    'CLIP_PRETRAINED_MODEL_ARCHIVE_LIST',
					    'CLIPModel',
					    'CLIPPreTrainedModel',
					    'CLIPTextModel',
					    'CLIPTextModelWithProjection',
					    'CLIPVisionModel',
					    'CLIPVisionModelWithProjection',
					]

try:
					if not is_tf_available():
										raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
					pass
else:
					snake_case_			:     List[Any]  	=  [
					    'TF_CLIP_PRETRAINED_MODEL_ARCHIVE_LIST',
					    'TFCLIPModel',
					    'TFCLIPPreTrainedModel',
					    'TFCLIPTextModel',
					    'TFCLIPVisionModel',
					]

try:
					if not is_flax_available():
										raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
					pass
else:
					snake_case_			:     Optional[int]  	=  [
					    'FlaxCLIPModel',
					    'FlaxCLIPPreTrainedModel',
					    'FlaxCLIPTextModel',
					    'FlaxCLIPTextPreTrainedModel',
					    'FlaxCLIPVisionModel',
					    'FlaxCLIPVisionPreTrainedModel',
					]


if TYPE_CHECKING:
					from .configuration_clip import (
					    CLIP_PRETRAINED_CONFIG_ARCHIVE_MAP,
					    CLIPConfig,
					    CLIPOnnxConfig,
					    CLIPTextConfig,
					    CLIPVisionConfig,
					)
					from .processing_clip import CLIPProcessor
					from .tokenization_clip import CLIPTokenizer

					try:
										if not is_tokenizers_available():
															raise OptionalDependencyNotAvailable()
					except OptionalDependencyNotAvailable:
										pass
					else:
										from .tokenization_clip_fast import CLIPTokenizerFast

					try:
										if not is_vision_available():
															raise OptionalDependencyNotAvailable()
					except OptionalDependencyNotAvailable:
										pass
					else:
										from .feature_extraction_clip import CLIPFeatureExtractor
										from .image_processing_clip import CLIPImageProcessor

					try:
										if not is_torch_available():
															raise OptionalDependencyNotAvailable()
					except OptionalDependencyNotAvailable:
										pass
					else:
										from .modeling_clip import (
										    CLIP_PRETRAINED_MODEL_ARCHIVE_LIST,
										    CLIPModel,
										    CLIPPreTrainedModel,
										    CLIPTextModel,
										    CLIPTextModelWithProjection,
										    CLIPVisionModel,
										    CLIPVisionModelWithProjection,
										)

					try:
										if not is_tf_available():
															raise OptionalDependencyNotAvailable()
					except OptionalDependencyNotAvailable:
										pass
					else:
										from .modeling_tf_clip import (
										    TF_CLIP_PRETRAINED_MODEL_ARCHIVE_LIST,
										    TFCLIPModel,
										    TFCLIPPreTrainedModel,
										    TFCLIPTextModel,
										    TFCLIPVisionModel,
										)

					try:
										if not is_flax_available():
															raise OptionalDependencyNotAvailable()
					except OptionalDependencyNotAvailable:
										pass
					else:
										from .modeling_flax_clip import (
										    FlaxCLIPModel,
										    FlaxCLIPPreTrainedModel,
										    FlaxCLIPTextModel,
										    FlaxCLIPTextPreTrainedModel,
										    FlaxCLIPVisionModel,
										    FlaxCLIPVisionPreTrainedModel,
										)


else:
					import sys

					snake_case_			:     str  	=  _LazyModule(__name__, globals()['__file__'], _import_structure, module_spec=__spec__)


