

from __future__ import annotations

import collections
import tempfile
import unittest

import numpy as np

from transformers.testing_utils import require_tf, require_vision, slow
from transformers.utils import is_tf_available, is_vision_available

from ...test_modeling_tf_common import floats_tensor, ids_tensor, random_attention_mask
from ..bert.test_modeling_tf_bert import TFBertModelTester
from ..clip.test_modeling_tf_clip import TFCLIPVisionModelTester
from ..deit.test_modeling_tf_deit import TFDeiTModelTester
from ..roberta.test_modeling_tf_roberta import TFRobertaModelTester
from ..vit.test_modeling_tf_vit import TFViTModelTester


if is_tf_available():
							from transformers import (
							    TFBertModel,
							    TFCLIPVisionModel,
							    TFDeiTModel,
							    TFRobertaModel,
							    TFVisionTextDualEncoderModel,
							    TFViTModel,
							    VisionTextDualEncoderConfig,
							)

if is_vision_available():
							from PIL import Image

							from transformers import VisionTextDualEncoderProcessor






def 					lowerCamelCase_     (							UpperCAmelCase_							:     int	)						->				Any:




	'''simple docstring'''




	if isinstance(UpperCAmelCase_							,       collections.abc.Iterable	):
		return x
	return (x, x)







@require_tf
class 	lowercase    :


		"""simple docstring"""




		def 		A__					(				self	,       __snake_case	,       __snake_case):
			pass


		def 		A__					(				self):
			pass


		def 		A__					(				self):
			pass


		def 		A__					(				self	,       __snake_case	,       __snake_case	,       __snake_case	,       __snake_case	,       __snake_case=None	,       **__snake_case):
			_UpperCamelCase   :		int			=						VisionTextDualEncoderConfig.from_vision_text_configs(__snake_case	,       __snake_case)

			_UpperCamelCase   :		int			=						TFVisionTextDualEncoderModel(__snake_case)

			_UpperCamelCase   :		str			=						model(input_ids=__snake_case	,       pixel_values=__snake_case	,       attention_mask=__snake_case)

			self.assertEqual(output['text_embeds'].shape	,       (input_ids.shape[0], config.projection_dim))
			self.assertEqual(output['image_embeds'].shape	,       (pixel_values.shape[0], config.projection_dim))


		def 		A__					(				self	,       __snake_case	,       __snake_case	,       __snake_case	,       __snake_case	,       __snake_case=None	,       **__snake_case):
			_UpperCamelCase	,		_UpperCamelCase   :		Optional[Any]			=						self.get_vision_text_model(__snake_case	,       __snake_case)
			_UpperCamelCase   :		List[str]			=						TFVisionTextDualEncoderModel(vision_model=__snake_case	,       text_model=__snake_case)

			_UpperCamelCase   :		str			=						model(input_ids=__snake_case	,       pixel_values=__snake_case	,       attention_mask=__snake_case)

			self.assertEqual(output['text_embeds'].shape	,       (input_ids.shape[0], model.config.projection_dim))
			self.assertEqual(output['image_embeds'].shape	,       (pixel_values.shape[0], model.config.projection_dim))


		def 		A__					(				self	,       __snake_case	,       __snake_case	,       __snake_case	,       __snake_case	,       __snake_case=None	,       **__snake_case):
			_UpperCamelCase	,		_UpperCamelCase   :		List[Any]			=						self.get_vision_text_model(__snake_case	,       __snake_case)
			_UpperCamelCase   :		List[str]			=						{'vision_model': vision_model, 'text_model': text_model}
			_UpperCamelCase   :		Dict			=						TFVisionTextDualEncoderModel.from_vision_text_pretrained(**__snake_case)

			_UpperCamelCase   :		List[Any]			=						model(input_ids=__snake_case	,       pixel_values=__snake_case	,       attention_mask=__snake_case)

			self.assertEqual(output['text_embeds'].shape	,       (input_ids.shape[0], model.config.projection_dim))
			self.assertEqual(output['image_embeds'].shape	,       (pixel_values.shape[0], model.config.projection_dim))


		def 		A__					(				self	,       __snake_case	,       __snake_case	,       __snake_case	,       __snake_case	,       __snake_case=None	,       **__snake_case):
			_UpperCamelCase	,		_UpperCamelCase   :		Union[str, Any]			=						self.get_vision_text_model(__snake_case	,       __snake_case)
			_UpperCamelCase   :		List[Any]			=						TFVisionTextDualEncoderModel(vision_model=__snake_case	,       text_model=__snake_case)

			_UpperCamelCase   :		Optional[Any]			=						model(input_ids=__snake_case	,       pixel_values=__snake_case	,       attention_mask=__snake_case)
			_UpperCamelCase   :		int			=						output[0].numpy()

			with tempfile.TemporaryDirectory() as tmpdirname:
				model.save_pretrained(__snake_case)
				_UpperCamelCase   :		Optional[int]			=						TFVisionTextDualEncoderModel.from_pretrained(__snake_case)

				_UpperCamelCase   :		Dict			=						model(input_ids=__snake_case	,       pixel_values=__snake_case	,       attention_mask=__snake_case)
				_UpperCamelCase   :		str			=						after_output[0].numpy()
				_UpperCamelCase   :		Optional[int]			=						np.amax(np.abs(out_a - out_a))
				self.assertLessEqual(__snake_case	,       1e-5)


		def 		A__					(				self	,       __snake_case	,       __snake_case	,       __snake_case	,       __snake_case	,       __snake_case=None	,       **__snake_case):
			_UpperCamelCase	,		_UpperCamelCase   :		List[Any]			=						self.get_vision_text_model(__snake_case	,       __snake_case)
			_UpperCamelCase   :		Tuple			=						TFVisionTextDualEncoderModel(vision_model=__snake_case	,       text_model=__snake_case)

			_UpperCamelCase   :		Tuple			=						model(
			    input_ids=__snake_case	,       pixel_values=__snake_case	,       attention_mask=__snake_case	,       output_attentions=__snake_case)

			_UpperCamelCase   :		str			=						output.vision_model_output.attentions
			self.assertEqual(len(__snake_case)	,       vision_config.num_hidden_layers)

			# in ViT, the seq_len equals the number of patches + 1 (we add 1 for the [CLS] token)
			_UpperCamelCase   :		int			=						to_atuple(vision_model.config.image_size)
			_UpperCamelCase   :		int			=						to_atuple(vision_model.config.patch_size)
			_UpperCamelCase   :		Tuple			=						(image_size[1] // patch_size[1]) * (image_size[0] // patch_size[0])
			_UpperCamelCase   :		Union[str, Any]			=						num_patches + 1
			self.assertEqual(vision_attentions[0].shape[-3:]	,       (vision_config.num_attention_heads, seq_len, seq_len))

			_UpperCamelCase   :		List[Any]			=						output.text_model_output.attentions
			self.assertEqual(len(__snake_case)	,       text_config.num_hidden_layers)

			self.assertEqual(
			    text_attentions[0].shape[-3:]	,       (text_config.num_attention_heads, input_ids.shape[-1], input_ids.shape[-1])	,       )


		def 		A__					(				self	,       __snake_case	,       __snake_case	,       __snake_case):
			_UpperCamelCase   :		Optional[int]			=						np.abs((a - b)).max()
			self.assertLessEqual(__snake_case	,       __snake_case	,       f'''Difference between torch and flax is {diff} (>= {tol}).''')


		def 		A__					(				self):
			_UpperCamelCase   :		str			=						self.prepare_config_and_inputs()
			self.check_vision_text_dual_encoder_model(**__snake_case)


		def 		A__					(				self):
			_UpperCamelCase   :		Optional[Any]			=						self.prepare_config_and_inputs()
			self.check_model_from_pretrained_configs(**__snake_case)


		def 		A__					(				self):
			_UpperCamelCase   :		Optional[Any]			=						self.prepare_config_and_inputs()
			self.check_vision_text_dual_encoder_from_pretrained(**__snake_case)


		def 		A__					(				self):
			_UpperCamelCase   :		Dict			=						self.prepare_config_and_inputs()
			self.check_save_load(**__snake_case)


		def 		A__					(				self):
			_UpperCamelCase   :		Tuple			=						self.prepare_config_and_inputs()
			self.check_vision_text_output_attention(**__snake_case)






		@slow
		def 		A__					(				self):
			_UpperCamelCase	,		_UpperCamelCase   :		Optional[Any]			=						self.get_pretrained_model_and_inputs()

			_UpperCamelCase   :		Optional[Any]			=						model_a(**__snake_case)
			_UpperCamelCase   :		str			=						outputs[0].numpy()

			with tempfile.TemporaryDirectory() as tmp_dirname:
				model_a.save_pretrained(__snake_case)
				_UpperCamelCase   :		Union[str, Any]			=						TFVisionTextDualEncoderModel.from_pretrained(__snake_case)

				_UpperCamelCase   :		str			=						model_a(**__snake_case)
				_UpperCamelCase   :		Optional[int]			=						after_outputs[0].numpy()
				_UpperCamelCase   :		Tuple			=						np.amax(np.abs(out_a - out_a))
				self.assertLessEqual(__snake_case	,       1e-5)







@require_tf
class 	lowercase    (				_lowercase    ,							unittest.TestCase							):


		"""simple docstring"""




		def 		A__					(				self):
			_UpperCamelCase   :		Union[str, Any]			=						TFVisionTextDualEncoderModel.from_vision_text_pretrained(
			    'hf-internal-testing/tiny-random-vit'	,       'hf-internal-testing/tiny-random-bert')
			_UpperCamelCase   :		List[Any]			=						13
			_UpperCamelCase   :		Any			=						floats_tensor(
			    [
			        batch_size,
			        model.vision_model.config.num_channels,
			        model.vision_model.config.image_size,
			        model.vision_model.config.image_size,
			    ])
			_UpperCamelCase   :		Any			=						ids_tensor([batch_size, 4]	,       model.text_model.config.vocab_size)
			_UpperCamelCase   :		str			=						random_attention_mask([batch_size, 4])
			_UpperCamelCase   :		Any			=						{'pixel_values': pixel_values, 'input_ids': input_ids, 'attention_mask': attention_mask}

			return model, inputs


		def 		A__					(				self	,       __snake_case	,       __snake_case):
			_UpperCamelCase   :		Tuple			=						TFViTModel(__snake_case	,       name='vision_model')
			_UpperCamelCase   :		Dict			=						TFBertModel(__snake_case	,       name='text_model')
			return vision_model, text_model






		def 		A__					(				self):
			_UpperCamelCase   :		Tuple			=						TFViTModelTester(self)
			_UpperCamelCase   :		int			=						TFBertModelTester(self)
			_UpperCamelCase   :		List[Any]			=						vit_model_tester.prepare_config_and_inputs()
			_UpperCamelCase   :		Dict			=						bert_model_tester.prepare_config_and_inputs()

			_UpperCamelCase	,		_UpperCamelCase	,		_UpperCamelCase   :		Tuple			=						vision_config_and_inputs

			(
			    (
			    _UpperCamelCase
			)	,		(
			    _UpperCamelCase
			)	,		(
			    _UpperCamelCase
			)	,		(
			    _UpperCamelCase
			)	,		(
			    _UpperCamelCase
			)	,		(
			    _UpperCamelCase
			)	,		(
			    _UpperCamelCase
			)	,		
			)   :		int			=						text_config_and_inputs

			return {
			    "text_config": text_config,
			    "vision_config": vision_config,
			    "pixel_values": pixel_values,
			    "attention_mask": input_mask,
			    "input_ids": input_ids,
			    "text_token_type_ids": token_type_ids,
			    "text_sequence_labels": sequence_labels,
			    "text_token_labels": token_labels,
			    "text_choice_labels": choice_labels,
			}







@require_tf
class 	lowercase    (				_lowercase    ,							unittest.TestCase							):


		"""simple docstring"""




		def 		A__					(				self):
			# DeiT repo doesn't have TF weights, but we don't actually use the weights at all so let's
			# just reinitialize it.
			_UpperCamelCase   :		Dict			=						TFVisionTextDualEncoderModel.from_vision_text_pretrained(
			    'Rocketknight1/tiny-random-deit-tf'	,       'hf-internal-testing/tiny-random-roberta')
			_UpperCamelCase   :		Dict			=						13
			_UpperCamelCase   :		Tuple			=						floats_tensor(
			    [
			        batch_size,
			        model.vision_model.config.num_channels,
			        model.vision_model.config.image_size,
			        model.vision_model.config.image_size,
			    ])
			_UpperCamelCase   :		Tuple			=						ids_tensor([batch_size, 4]	,       model.text_model.config.vocab_size)
			_UpperCamelCase   :		Tuple			=						random_attention_mask([batch_size, 4])
			_UpperCamelCase   :		str			=						{'pixel_values': pixel_values, 'input_ids': input_ids, 'attention_mask': attention_mask}

			return model, inputs


		def 		A__					(				self	,       __snake_case	,       __snake_case	,       __snake_case	,       __snake_case	,       __snake_case=None	,       **__snake_case):
			_UpperCamelCase	,		_UpperCamelCase   :		Optional[int]			=						self.get_vision_text_model(__snake_case	,       __snake_case)
			_UpperCamelCase   :		Tuple			=						TFVisionTextDualEncoderModel(vision_model=__snake_case	,       text_model=__snake_case)

			_UpperCamelCase   :		List[str]			=						model(
			    input_ids=__snake_case	,       pixel_values=__snake_case	,       attention_mask=__snake_case	,       output_attentions=__snake_case)

			_UpperCamelCase   :		str			=						output.vision_model_output.attentions
			self.assertEqual(len(__snake_case)	,       vision_config.num_hidden_layers)

			# in DEiT, the seq_len equals the number of patches + 2 (we add 2 for the [CLS] and distillation tokens)
			_UpperCamelCase   :		List[str]			=						to_atuple(vision_model.config.image_size)
			_UpperCamelCase   :		Union[str, Any]			=						to_atuple(vision_model.config.patch_size)
			_UpperCamelCase   :		str			=						(image_size[1] // patch_size[1]) * (image_size[0] // patch_size[0])
			_UpperCamelCase   :		str			=						num_patches + 2
			self.assertEqual(vision_attentions[0].shape[-3:]	,       (vision_config.num_attention_heads, seq_len, seq_len))

			_UpperCamelCase   :		Tuple			=						output.text_model_output.attentions
			self.assertEqual(len(__snake_case)	,       text_config.num_hidden_layers)

			self.assertEqual(
			    text_attentions[0].shape[-3:]	,       (text_config.num_attention_heads, input_ids.shape[-1], input_ids.shape[-1])	,       )


		def 		A__					(				self	,       __snake_case	,       __snake_case):
			_UpperCamelCase   :		str			=						TFDeiTModel(__snake_case	,       name='vision_model')
			_UpperCamelCase   :		Dict			=						TFRobertaModel(__snake_case	,       name='text_model')
			return vision_model, text_model






		def 		A__					(				self):
			_UpperCamelCase   :		List[str]			=						TFDeiTModelTester(self)
			_UpperCamelCase   :		int			=						TFRobertaModelTester(self)
			_UpperCamelCase   :		int			=						vit_model_tester.prepare_config_and_inputs()
			_UpperCamelCase   :		Optional[Any]			=						bert_model_tester.prepare_config_and_inputs()

			_UpperCamelCase	,		_UpperCamelCase	,		_UpperCamelCase   :		str			=						vision_config_and_inputs

			(
			    (
			    _UpperCamelCase
			)	,		(
			    _UpperCamelCase
			)	,		(
			    _UpperCamelCase
			)	,		(
			    _UpperCamelCase
			)	,		(
			    _UpperCamelCase
			)	,		(
			    _UpperCamelCase
			)	,		(
			    _UpperCamelCase
			)	,		
			)   :		List[Any]			=						text_config_and_inputs

			return {
			    "text_config": text_config,
			    "vision_config": vision_config,
			    "pixel_values": pixel_values,
			    "attention_mask": input_mask,
			    "input_ids": input_ids,
			    "text_token_type_ids": token_type_ids,
			    "text_sequence_labels": sequence_labels,
			    "text_token_labels": token_labels,
			    "text_choice_labels": choice_labels,
			}







@require_tf
class 	lowercase    (				_lowercase    ,							unittest.TestCase							):


		"""simple docstring"""




		def 		A__					(				self):
			_UpperCamelCase   :		Optional[int]			=						TFVisionTextDualEncoderModel.from_vision_text_pretrained(
			    'Rocketknight1/tiny-random-clip-tf'	,       'hf-internal-testing/tiny-random-bert')
			_UpperCamelCase   :		List[Any]			=						13
			_UpperCamelCase   :		Tuple			=						floats_tensor(
			    [
			        batch_size,
			        model.vision_model.config.num_channels,
			        model.vision_model.config.image_size,
			        model.vision_model.config.image_size,
			    ])
			_UpperCamelCase   :		Optional[Any]			=						ids_tensor([batch_size, 4]	,       model.text_model.config.vocab_size)
			_UpperCamelCase   :		str			=						random_attention_mask([batch_size, 4])
			_UpperCamelCase   :		Tuple			=						{'pixel_values': pixel_values, 'input_ids': input_ids, 'attention_mask': attention_mask}

			return model, inputs


		def 		A__					(				self	,       __snake_case	,       __snake_case):
			_UpperCamelCase   :		Dict			=						TFCLIPVisionModel(__snake_case	,       name='vision_model')
			_UpperCamelCase   :		Tuple			=						TFBertModel(__snake_case	,       name='text_model')
			return vision_model, text_model






		def 		A__					(				self):
			_UpperCamelCase   :		int			=						TFCLIPVisionModelTester(self)
			_UpperCamelCase   :		str			=						TFBertModelTester(self)
			_UpperCamelCase   :		Union[str, Any]			=						clip_model_tester.prepare_config_and_inputs()
			_UpperCamelCase   :		Tuple			=						bert_model_tester.prepare_config_and_inputs()

			_UpperCamelCase	,		_UpperCamelCase   :		List[str]			=						vision_config_and_inputs

			(
			    (
			    _UpperCamelCase
			)	,		(
			    _UpperCamelCase
			)	,		(
			    _UpperCamelCase
			)	,		(
			    _UpperCamelCase
			)	,		(
			    _UpperCamelCase
			)	,		(
			    _UpperCamelCase
			)	,		(
			    _UpperCamelCase
			)	,		
			)   :		Optional[int]			=						text_config_and_inputs

			return {
			    "text_config": text_config,
			    "vision_config": vision_config,
			    "pixel_values": pixel_values,
			    "attention_mask": input_mask,
			    "input_ids": input_ids,
			    "text_token_type_ids": token_type_ids,
			    "text_sequence_labels": sequence_labels,
			    "text_token_labels": token_labels,
			    "text_choice_labels": choice_labels,
			}







@require_vision
@require_tf
class 	lowercase    (				unittest.TestCase							):


		"""simple docstring"""




		@slow
		def 		A__					(				self):
			_UpperCamelCase   :		Tuple			=						TFVisionTextDualEncoderModel.from_pretrained(
			    'clip-italian/clip-italian'	,       logit_scale_init_value=1.0	,       from_pt=__snake_case)
			_UpperCamelCase   :		str			=						VisionTextDualEncoderProcessor.from_pretrained('clip-italian/clip-italian')

			_UpperCamelCase   :		Dict			=						Image.open('./tests/fixtures/tests_samples/COCO/000000039769.png')
			_UpperCamelCase   :		str			=						processor(
			    text=['una foto di un gatto', 'una foto di un cane']	,       images=__snake_case	,       padding=__snake_case	,       return_tensors='np')

			_UpperCamelCase   :		Union[str, Any]			=						model(**__snake_case)

			# verify the logits
			self.assertEqual(outputs.logits_per_image.shape	,       (inputs.pixel_values.shape[0], inputs.input_ids.shape[0]))
			self.assertEqual(
			    outputs.logits_per_text.shape	,       (inputs.input_ids.shape[0], inputs.pixel_values.shape[0])	,       )

			_UpperCamelCase   :		List[Any]			=						np.array([[1.2_2_8_4_7_2_7, 0.3_1_0_4_1_2_2]])

			self.assertTrue(np.allclose(outputs.logits_per_image.numpy()	,       __snake_case	,       atol=1e-3))







lowerCAmelCase__								=		range(2, 2_0 + 1)
lowerCAmelCase__								=		[1_0**k for k in range(ks[-1] + 1)]
lowerCAmelCase__								=		{}






def 					lowerCamelCase_     (							UpperCAmelCase_							:     Optional[Any]							,       UpperCAmelCase_							:     List[str]							,       UpperCAmelCase_							:     Any							,       UpperCAmelCase_							:     int	)						->				Tuple:




	'''simple docstring'''




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

	_UpperCamelCase	,		_UpperCamelCase   :		Dict			=						0, 0
	_UpperCamelCase   :		Optional[int]			=						n - i

	_UpperCamelCase   :		Union[str, Any]			=						memo.get(UpperCAmelCase_	)

	if sub_memo is not None:
		_UpperCamelCase   :		str			=						sub_memo.get(UpperCAmelCase_	)

		if jumps is not None and len(UpperCAmelCase_	) > 0:
			# find and make the largest jump without going over
			_UpperCamelCase   :		str			=						-1
			for _k in range(len(UpperCAmelCase_	) - 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   :		Optional[Any]			=						jumps[max_jump]
				# since the difference between jumps is cached, add c
				_UpperCamelCase   :		Tuple			=						diff + c
				for j in range(min(UpperCAmelCase_							,       len(UpperCAmelCase_	)	)	):
					_UpperCamelCase	,		_UpperCamelCase   :		Dict			=						divmod(UpperCAmelCase_							,       1_0	)
				if new_c > 0:
					add(UpperCAmelCase_							,       UpperCAmelCase_							,       UpperCAmelCase_	)

		else:
			_UpperCamelCase   :		Union[str, Any]			=						[]
	else:
		_UpperCamelCase   :		List[Any]			=						{c: []}
		_UpperCamelCase   :		Optional[int]			=						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   :		Optional[Any]			=						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	,		_UpperCamelCase   :		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 					lowerCamelCase_     (							UpperCAmelCase_							:     int							,       UpperCAmelCase_							:     Dict							,       UpperCAmelCase_							:     Any							,       UpperCAmelCase_							:     Any	)						->				Dict:




	'''simple docstring'''




	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   :		Any			=						i
	_UpperCamelCase	,		_UpperCamelCase	,		_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   :		Union[str, Any]			=						ds_c + ds_b
		diff += addend
		_UpperCamelCase   :		Union[str, Any]			=						0
		for j in range(UpperCAmelCase_	):
			_UpperCamelCase   :		Union[str, Any]			=						a_i[j] + addend
			_UpperCamelCase	,		_UpperCamelCase   :		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 					lowerCamelCase_     (							UpperCAmelCase_							:     Union[str, Any]							,       UpperCAmelCase_							:     Optional[int]							,       UpperCAmelCase_							:     Any	)						->				Dict:




	'''simple docstring'''




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

		if addend == 0:
			break

	while addend > 0:
		_UpperCamelCase	,		_UpperCamelCase   :		Dict			=						divmod(UpperCAmelCase_							,       1_0	)
		digits.append(UpperCAmelCase_	)






def 					lowerCamelCase_     (							UpperCAmelCase_							:     int = 1_0**1_5	)						->				int:




	'''simple docstring'''




	_UpperCamelCase   :		Optional[Any]			=						[1]
	_UpperCamelCase   :		Optional[int]			=						1
	_UpperCamelCase   :		int			=						0
	while True:
		_UpperCamelCase	,		_UpperCamelCase   :		List[Any]			=						next_term(UpperCAmelCase_							,       2_0							,       i + dn							,       UpperCAmelCase_	)
		dn += terms_jumped
		if dn == n - i:
			break

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


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




