






a__     :   Tuple       =     range(2, 2_0 + 1)
a__     :   int       =     [1_0**k for k in range(ks[-1] + 1)]
a__     :   Tuple       =     {}

def _UpperCAmelCase   (	a						:	Any  ,					a						:	Optional[int]  ,					a						:	List[Any]  ,					a						:	str ):
							snake_case__	  =       sum(a_i[j] for j in range(SCREAMING_SNAKE_CASE_  ,					len(SCREAMING_SNAKE_CASE_ ) ) )
							snake_case__	  =       sum(a_i[j] * base[j] for j in range(min(len(SCREAMING_SNAKE_CASE_ )  ,					SCREAMING_SNAKE_CASE_ ) ) )

							snake_case__	  =       0, 0
							snake_case__	  =       n - i

							snake_case__	  =       memo.get(SCREAMING_SNAKE_CASE_ )

							if sub_memo is not None:
														snake_case__	  =       sub_memo.get(SCREAMING_SNAKE_CASE_ )

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

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

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

							snake_case__	  =       sub_memo[c]

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

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

def _UpperCAmelCase   (	a						:	List[Any]  ,					a						:	str  ,					a						:	Tuple  ,					a						:	Optional[Any] ):
							if i >= n:
														return 0, i
							if k > len(SCREAMING_SNAKE_CASE_ ):
														a_i.extend([0 for _ in range(k - len(SCREAMING_SNAKE_CASE_ ) )] )

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

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

																					ds_c += a_i[j]

														if addend > 0:
																					break

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

def _UpperCAmelCase   (	a						:	Union[str, Any]  ,					a						:	Tuple  ,					a						:	Dict ):
							for j in range(SCREAMING_SNAKE_CASE_  ,					len(SCREAMING_SNAKE_CASE_ ) ):
														snake_case__	  =       digits[j] + addend
														if s >= 10:
																					snake_case__	  =       divmod(SCREAMING_SNAKE_CASE_  ,					10 )
																					snake_case__	  =       addend // 10 + quotient
														else:
																					snake_case__	  =       s
																					snake_case__	  =       addend // 10

														if addend == 0:
																					break

							while addend > 0:
														snake_case__	  =       divmod(SCREAMING_SNAKE_CASE_  ,					10 )
														digits.append(SCREAMING_SNAKE_CASE_ )

def _UpperCAmelCase   (	a						:	int = 10**15 ):
							snake_case__	  =       [1]
							snake_case__	  =       1
							snake_case__	  =       0
							while True:
														snake_case__	  =       next_term(SCREAMING_SNAKE_CASE_  ,					20  ,					i + dn  ,					SCREAMING_SNAKE_CASE_ )
														dn += terms_jumped
														if dn == n - i:
																					break

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


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








import unittest

import torch

from diffusers import VQModel
from diffusers.utils import floats_tensor, torch_device
from diffusers.utils.testing_utils import enable_full_determinism

from .test_modeling_common import ModelTesterMixin, UNetTesterMixin


enable_full_determinism()


class    _lowerCAmelCase			(		lowercase_     ,      lowercase_     ,      unittest.TestCase      ):



				"""simple docstring"""



				_lowercase				:   Optional[int]      =  VQModel
				_lowercase				:   str      =  '''sample'''



				@property
				def 					__magic_name__							(      self    :    Union[str, Any]			,		UpperCamelCase__    :    Tuple=(3_2, 3_2)):






											'''simple docstring'''







											snake_case__	  =       4
											snake_case__	  =       3

											snake_case__	  =       floats_tensor((batch_size, num_channels) + sizes).to(UpperCamelCase__)

											return {"sample": image}



				@property
				def 					__magic_name__							(      self    :    str):






											'''simple docstring'''







											return (3, 3_2, 3_2)



				@property
				def 					__magic_name__							(      self    :    List[str]):






											'''simple docstring'''







											return (3, 3_2, 3_2)



				def 					__magic_name__							(      self    :    int):






											'''simple docstring'''







											snake_case__	  =       {
											    """block_out_channels""": [3_2, 6_4],
											    """in_channels""": 3,
											    """out_channels""": 3,
											    """down_block_types""": ["""DownEncoderBlock2D""", """DownEncoderBlock2D"""],
											    """up_block_types""": ["""UpDecoderBlock2D""", """UpDecoderBlock2D"""],
											    """latent_channels""": 3,
											}
											snake_case__	  =       self.dummy_input
											return init_dict, inputs_dict



				def 					__magic_name__							(      self    :    Optional[int]):






											'''simple docstring'''







											pass



				def 					__magic_name__							(      self    :    Tuple):






											'''simple docstring'''







											pass



				def 					__magic_name__							(      self    :    str):






											'''simple docstring'''







											snake_case__  , snake_case__	  =       VQModel.from_pretrained("""fusing/vqgan-dummy"""			,		output_loading_info=UpperCamelCase__)
											self.assertIsNotNone(UpperCamelCase__)
											self.assertEqual(len(loading_info["""missing_keys"""])			,		0)

											model.to(UpperCamelCase__)
											snake_case__	  =       model(**self.dummy_input)

											assert image is not None, "Make sure output is not None"



				def 					__magic_name__							(      self    :    Dict):






											'''simple docstring'''







											snake_case__	  =       VQModel.from_pretrained("""fusing/vqgan-dummy""")
											model.to(UpperCamelCase__).eval()

											torch.manual_seed(0)
											if torch.cuda.is_available():
																		torch.cuda.manual_seed_all(0)

											snake_case__	  =       torch.randn(1			,		model.config.in_channels			,		model.config.sample_size			,		model.config.sample_size)
											snake_case__	  =       image.to(UpperCamelCase__)
											with torch.no_grad():
																		snake_case__	  =       model(UpperCamelCase__).sample

											snake_case__	  =       output[0, -1, -3:, -3:].flatten().cpu()
											# fmt: off
											snake_case__	  =       torch.tensor([-0.01_53, -0.40_44, -0.18_80, -0.51_61, -0.24_18, -0.40_72, -0.16_12, -0.06_33, -0.01_43])
											# fmt: on
											self.assertTrue(torch.allclose(UpperCamelCase__			,		UpperCamelCase__			,		atol=1E-3))
