




import argparse
import json
from pathlib import Path

import requests
import torch
from huggingface_hub import cached_download, hf_hub_download, hf_hub_url
from PIL import Image

from transformers import DetaConfig, DetaForObjectDetection, DetaImageProcessor, SwinConfig
from transformers.utils import logging


logging.set_verbosity_info()
UpperCAmelCase_		:					Optional[Any]          =  logging.get_logger(__name__)




def 		lowerCAmelCase_ (						lowerCamelCase ):
				__magic_name__						:						Tuple										=SwinConfig(
				    embed_dim=192						,  depths=(2, 2, 18, 2)						,  num_heads=(6, 12, 24, 48)						,  window_size=12						,  out_features=["""stage2""", """stage3""", """stage4"""]						,  )

				__magic_name__						:						Tuple										=DetaConfig(
				    backbone_config=lowerCamelCase						,  num_queries=900						,  encoder_ffn_dim=2048						,  decoder_ffn_dim=2048						,  num_feature_levels=5						,  assign_first_stage=lowerCamelCase						,  with_box_refine=lowerCamelCase						,  two_stage=lowerCamelCase						,  )

				# set labels
				__magic_name__						:						Optional[Any]										="""huggingface/label-files"""
				if "o365" in model_name:
								__magic_name__						:						int										=366
								__magic_name__						:						Any										="""object365-id2label.json"""
				else:
								__magic_name__						:						Optional[int]										=91
								__magic_name__						:						Any										="""coco-detection-id2label.json"""

				__magic_name__						:						Union[str, Any]										=num_labels
				__magic_name__						:						Any										=json.load(open(cached_download(hf_hub_url(lowerCamelCase						,  lowerCamelCase						,  repo_type="""dataset""" ) )						,  """r""" ) )
				__magic_name__						:						Union[str, Any]										={int(lowerCamelCase ): v for k, v in idalabel.items()}
				__magic_name__						:						Union[str, Any]										=idalabel
				__magic_name__						:						Tuple										={v: k for k, v in idalabel.items()}

				return config




def 		lowerCAmelCase_ (						lowerCamelCase ):
				__magic_name__						:						str										=[]

				# stem
				# fmt: off
				rename_keys.append(("""backbone.0.body.patch_embed.proj.weight""", """model.backbone.model.embeddings.patch_embeddings.projection.weight""") )
				rename_keys.append(("""backbone.0.body.patch_embed.proj.bias""", """model.backbone.model.embeddings.patch_embeddings.projection.bias""") )
				rename_keys.append(("""backbone.0.body.patch_embed.norm.weight""", """model.backbone.model.embeddings.norm.weight""") )
				rename_keys.append(("""backbone.0.body.patch_embed.norm.bias""", """model.backbone.model.embeddings.norm.bias""") )
				# stages
				for i in range(len(config.backbone_config.depths ) ):
								for j in range(config.backbone_config.depths[i] ):
												rename_keys.append((F"backbone.0.body.layers.{i}.blocks.{j}.norm1.weight", F"model.backbone.model.encoder.layers.{i}.blocks.{j}.layernorm_before.weight") )
												rename_keys.append((F"backbone.0.body.layers.{i}.blocks.{j}.norm1.bias", F"model.backbone.model.encoder.layers.{i}.blocks.{j}.layernorm_before.bias") )
												rename_keys.append((F"backbone.0.body.layers.{i}.blocks.{j}.attn.relative_position_bias_table", F"model.backbone.model.encoder.layers.{i}.blocks.{j}.attention.self.relative_position_bias_table") )
												rename_keys.append((F"backbone.0.body.layers.{i}.blocks.{j}.attn.relative_position_index", F"model.backbone.model.encoder.layers.{i}.blocks.{j}.attention.self.relative_position_index") )
												rename_keys.append((F"backbone.0.body.layers.{i}.blocks.{j}.attn.proj.weight", F"model.backbone.model.encoder.layers.{i}.blocks.{j}.attention.output.dense.weight") )
												rename_keys.append((F"backbone.0.body.layers.{i}.blocks.{j}.attn.proj.bias", F"model.backbone.model.encoder.layers.{i}.blocks.{j}.attention.output.dense.bias") )
												rename_keys.append((F"backbone.0.body.layers.{i}.blocks.{j}.norm2.weight", F"model.backbone.model.encoder.layers.{i}.blocks.{j}.layernorm_after.weight") )
												rename_keys.append((F"backbone.0.body.layers.{i}.blocks.{j}.norm2.bias", F"model.backbone.model.encoder.layers.{i}.blocks.{j}.layernorm_after.bias") )
												rename_keys.append((F"backbone.0.body.layers.{i}.blocks.{j}.mlp.fc1.weight", F"model.backbone.model.encoder.layers.{i}.blocks.{j}.intermediate.dense.weight") )
												rename_keys.append((F"backbone.0.body.layers.{i}.blocks.{j}.mlp.fc1.bias", F"model.backbone.model.encoder.layers.{i}.blocks.{j}.intermediate.dense.bias") )
												rename_keys.append((F"backbone.0.body.layers.{i}.blocks.{j}.mlp.fc2.weight", F"model.backbone.model.encoder.layers.{i}.blocks.{j}.output.dense.weight") )
												rename_keys.append((F"backbone.0.body.layers.{i}.blocks.{j}.mlp.fc2.bias", F"model.backbone.model.encoder.layers.{i}.blocks.{j}.output.dense.bias") )

								if i < 3:
												rename_keys.append((F"backbone.0.body.layers.{i}.downsample.reduction.weight", F"model.backbone.model.encoder.layers.{i}.downsample.reduction.weight") )
												rename_keys.append((F"backbone.0.body.layers.{i}.downsample.norm.weight", F"model.backbone.model.encoder.layers.{i}.downsample.norm.weight") )
												rename_keys.append((F"backbone.0.body.layers.{i}.downsample.norm.bias", F"model.backbone.model.encoder.layers.{i}.downsample.norm.bias") )

				rename_keys.append(("""backbone.0.body.norm1.weight""", """model.backbone.model.hidden_states_norms.stage2.weight""") )
				rename_keys.append(("""backbone.0.body.norm1.bias""", """model.backbone.model.hidden_states_norms.stage2.bias""") )
				rename_keys.append(("""backbone.0.body.norm2.weight""", """model.backbone.model.hidden_states_norms.stage3.weight""") )
				rename_keys.append(("""backbone.0.body.norm2.bias""", """model.backbone.model.hidden_states_norms.stage3.bias""") )
				rename_keys.append(("""backbone.0.body.norm3.weight""", """model.backbone.model.hidden_states_norms.stage4.weight""") )
				rename_keys.append(("""backbone.0.body.norm3.bias""", """model.backbone.model.hidden_states_norms.stage4.bias""") )

				# transformer encoder
				for i in range(config.encoder_layers ):
								rename_keys.append((F"transformer.encoder.layers.{i}.self_attn.sampling_offsets.weight", F"model.encoder.layers.{i}.self_attn.sampling_offsets.weight") )
								rename_keys.append((F"transformer.encoder.layers.{i}.self_attn.sampling_offsets.bias", F"model.encoder.layers.{i}.self_attn.sampling_offsets.bias") )
								rename_keys.append((F"transformer.encoder.layers.{i}.self_attn.attention_weights.weight", F"model.encoder.layers.{i}.self_attn.attention_weights.weight") )
								rename_keys.append((F"transformer.encoder.layers.{i}.self_attn.attention_weights.bias", F"model.encoder.layers.{i}.self_attn.attention_weights.bias") )
								rename_keys.append((F"transformer.encoder.layers.{i}.self_attn.value_proj.weight", F"model.encoder.layers.{i}.self_attn.value_proj.weight") )
								rename_keys.append((F"transformer.encoder.layers.{i}.self_attn.value_proj.bias", F"model.encoder.layers.{i}.self_attn.value_proj.bias") )
								rename_keys.append((F"transformer.encoder.layers.{i}.self_attn.output_proj.weight", F"model.encoder.layers.{i}.self_attn.output_proj.weight") )
								rename_keys.append((F"transformer.encoder.layers.{i}.self_attn.output_proj.bias", F"model.encoder.layers.{i}.self_attn.output_proj.bias") )
								rename_keys.append((F"transformer.encoder.layers.{i}.norm1.weight", F"model.encoder.layers.{i}.self_attn_layer_norm.weight") )
								rename_keys.append((F"transformer.encoder.layers.{i}.norm1.bias", F"model.encoder.layers.{i}.self_attn_layer_norm.bias") )
								rename_keys.append((F"transformer.encoder.layers.{i}.linear1.weight", F"model.encoder.layers.{i}.fc1.weight") )
								rename_keys.append((F"transformer.encoder.layers.{i}.linear1.bias", F"model.encoder.layers.{i}.fc1.bias") )
								rename_keys.append((F"transformer.encoder.layers.{i}.linear2.weight", F"model.encoder.layers.{i}.fc2.weight") )
								rename_keys.append((F"transformer.encoder.layers.{i}.linear2.bias", F"model.encoder.layers.{i}.fc2.bias") )
								rename_keys.append((F"transformer.encoder.layers.{i}.norm2.weight", F"model.encoder.layers.{i}.final_layer_norm.weight") )
								rename_keys.append((F"transformer.encoder.layers.{i}.norm2.bias", F"model.encoder.layers.{i}.final_layer_norm.bias") )

				# transformer decoder
				for i in range(config.decoder_layers ):
								rename_keys.append((F"transformer.decoder.layers.{i}.cross_attn.sampling_offsets.weight", F"model.decoder.layers.{i}.encoder_attn.sampling_offsets.weight") )
								rename_keys.append((F"transformer.decoder.layers.{i}.cross_attn.sampling_offsets.bias", F"model.decoder.layers.{i}.encoder_attn.sampling_offsets.bias") )
								rename_keys.append((F"transformer.decoder.layers.{i}.cross_attn.attention_weights.weight", F"model.decoder.layers.{i}.encoder_attn.attention_weights.weight") )
								rename_keys.append((F"transformer.decoder.layers.{i}.cross_attn.attention_weights.bias", F"model.decoder.layers.{i}.encoder_attn.attention_weights.bias") )
								rename_keys.append((F"transformer.decoder.layers.{i}.cross_attn.value_proj.weight", F"model.decoder.layers.{i}.encoder_attn.value_proj.weight") )
								rename_keys.append((F"transformer.decoder.layers.{i}.cross_attn.value_proj.bias", F"model.decoder.layers.{i}.encoder_attn.value_proj.bias") )
								rename_keys.append((F"transformer.decoder.layers.{i}.cross_attn.output_proj.weight", F"model.decoder.layers.{i}.encoder_attn.output_proj.weight") )
								rename_keys.append((F"transformer.decoder.layers.{i}.cross_attn.output_proj.bias", F"model.decoder.layers.{i}.encoder_attn.output_proj.bias") )
								rename_keys.append((F"transformer.decoder.layers.{i}.norm1.weight", F"model.decoder.layers.{i}.encoder_attn_layer_norm.weight") )
								rename_keys.append((F"transformer.decoder.layers.{i}.norm1.bias", F"model.decoder.layers.{i}.encoder_attn_layer_norm.bias") )
								rename_keys.append((F"transformer.decoder.layers.{i}.self_attn.out_proj.weight", F"model.decoder.layers.{i}.self_attn.out_proj.weight") )
								rename_keys.append((F"transformer.decoder.layers.{i}.self_attn.out_proj.bias", F"model.decoder.layers.{i}.self_attn.out_proj.bias") )
								rename_keys.append((F"transformer.decoder.layers.{i}.norm2.weight", F"model.decoder.layers.{i}.self_attn_layer_norm.weight") )
								rename_keys.append((F"transformer.decoder.layers.{i}.norm2.bias", F"model.decoder.layers.{i}.self_attn_layer_norm.bias") )
								rename_keys.append((F"transformer.decoder.layers.{i}.linear1.weight", F"model.decoder.layers.{i}.fc1.weight") )
								rename_keys.append((F"transformer.decoder.layers.{i}.linear1.bias", F"model.decoder.layers.{i}.fc1.bias") )
								rename_keys.append((F"transformer.decoder.layers.{i}.linear2.weight", F"model.decoder.layers.{i}.fc2.weight") )
								rename_keys.append((F"transformer.decoder.layers.{i}.linear2.bias", F"model.decoder.layers.{i}.fc2.bias") )
								rename_keys.append((F"transformer.decoder.layers.{i}.norm3.weight", F"model.decoder.layers.{i}.final_layer_norm.weight") )
								rename_keys.append((F"transformer.decoder.layers.{i}.norm3.bias", F"model.decoder.layers.{i}.final_layer_norm.bias") )

				# fmt: on

				return rename_keys




def 		lowerCAmelCase_ (						lowerCamelCase						,  lowerCamelCase						,  lowerCamelCase ):
				__magic_name__						:						str										=dct.pop(lowerCamelCase )
				__magic_name__						:						List[str]										=val




def 		lowerCAmelCase_ (						lowerCamelCase						,  lowerCamelCase ):
				__magic_name__						:						Tuple										=[int(backbone_config.embed_dim * 2**i ) for i in range(len(backbone_config.depths ) )]
				for i in range(len(backbone_config.depths ) ):
								__magic_name__						:						Optional[int]										=num_features[i]
								for j in range(backbone_config.depths[i] ):
												# fmt: off
												# read in weights + bias of input projection layer (in original implementation, this is a single matrix + bias)
												__magic_name__						:						List[str]										=state_dict.pop(F"backbone.0.body.layers.{i}.blocks.{j}.attn.qkv.weight" )
												__magic_name__						:						Any										=state_dict.pop(F"backbone.0.body.layers.{i}.blocks.{j}.attn.qkv.bias" )
												# next, add query, keys and values (in that order) to the state dict
												__magic_name__						:						List[Any]										=in_proj_weight[:dim, :]
												__magic_name__						:						Tuple										=in_proj_bias[: dim]
												__magic_name__						:						str										=in_proj_weight[
												    dim : dim * 2, :
												]
												__magic_name__						:						Optional[int]										=in_proj_bias[
												    dim : dim * 2
												]
												__magic_name__						:						Union[str, Any]										=in_proj_weight[
												    -dim :, :
												]
												__magic_name__						:						Tuple										=in_proj_bias[-dim :]
												# fmt: on




def 		lowerCAmelCase_ (						lowerCamelCase						,  lowerCamelCase ):
				# transformer decoder self-attention layers
				__magic_name__						:						Union[str, Any]										=config.d_model
				for i in range(config.decoder_layers ):
								# read in weights + bias of input projection layer of self-attention
								__magic_name__						:						Dict										=state_dict.pop(F"transformer.decoder.layers.{i}.self_attn.in_proj_weight" )
								__magic_name__						:						int										=state_dict.pop(F"transformer.decoder.layers.{i}.self_attn.in_proj_bias" )
								# next, add query, keys and values (in that order) to the state dict
								__magic_name__						:						int										=in_proj_weight[:hidden_size, :]
								__magic_name__						:						Tuple										=in_proj_bias[:hidden_size]
								__magic_name__						:						int										=in_proj_weight[
								    hidden_size : hidden_size * 2, :
								]
								__magic_name__						:						List[Any]										=in_proj_bias[hidden_size : hidden_size * 2]
								__magic_name__						:						str										=in_proj_weight[-hidden_size:, :]
								__magic_name__						:						str										=in_proj_bias[-hidden_size:]




def 		lowerCAmelCase_ (						):
				__magic_name__						:						int										="""http://images.cocodataset.org/val2017/000000039769.jpg"""
				__magic_name__						:						str										=Image.open(requests.get(lowerCamelCase						,  stream=lowerCamelCase ).raw )

				return im




@torch.no_grad()
def 		lowerCAmelCase_ (						lowerCamelCase						,  lowerCamelCase						,  lowerCamelCase ):
				__magic_name__						:						Dict										=get_deta_config(lowerCamelCase )

				# load original state dict
				if model_name == "deta-swin-large":
								__magic_name__						:						List[str]										=hf_hub_download(repo_id="""nielsr/deta-checkpoints"""						,  filename="""adet_swin_ft.pth""" )
				elif model_name == "deta-swin-large-o365":
								__magic_name__						:						Dict										=hf_hub_download(repo_id="""jozhang97/deta-swin-l-o365"""						,  filename="""deta_swin_pt_o365.pth""" )
				else:
								raise ValueError(F"Model name {model_name} not supported" )

				__magic_name__						:						int										=torch.load(lowerCamelCase						,  map_location="""cpu""" )["""model"""]

				# original state dict
				for name, param in state_dict.items():
								print(lowerCamelCase						,  param.shape )

				# rename keys
				__magic_name__						:						Any										=create_rename_keys(lowerCamelCase )
				for src, dest in rename_keys:
								rename_key(lowerCamelCase						,  lowerCamelCase						,  lowerCamelCase )
				read_in_swin_q_k_v(lowerCamelCase						,  config.backbone_config )
				read_in_decoder_q_k_v(lowerCamelCase						,  lowerCamelCase )

				# fix some prefixes
				for key in state_dict.copy().keys():
								if "transformer.decoder.class_embed" in key or "transformer.decoder.bbox_embed" in key:
												__magic_name__						:						Any										=state_dict.pop(lowerCamelCase )
												__magic_name__						:						Any										=val
								if "input_proj" in key:
												__magic_name__						:						List[str]										=state_dict.pop(lowerCamelCase )
												__magic_name__						:						Optional[Any]										=val
								if "level_embed" in key or "pos_trans" in key or "pix_trans" in key or "enc_output" in key:
												__magic_name__						:						int										=state_dict.pop(lowerCamelCase )
												__magic_name__						:						Any										=val

    # finally, create HuggingFace model and load state dict
				__magic_name__						:						str										=DetaForObjectDetection(lowerCamelCase )
				model.load_state_dict(lowerCamelCase )
				model.eval()

				__magic_name__						:						Optional[Any]										="""cuda""" if torch.cuda.is_available() else """cpu"""
				model.to(lowerCamelCase )

				# load image processor
				__magic_name__						:						Any										=DetaImageProcessor(format="""coco_detection""" )

				# verify our conversion on image
				__magic_name__						:						Tuple										=prepare_img()
				__magic_name__						:						Optional[Any]										=processor(images=lowerCamelCase						,  return_tensors="""pt""" )
				__magic_name__						:						int										=encoding["""pixel_values"""]
				__magic_name__						:						List[str]										=model(pixel_values.to(lowerCamelCase ) )

				# verify logits
				print("""Logits:"""						,  outputs.logits[0, :3, :3] )
				print("""Boxes:"""						,  outputs.pred_boxes[0, :3, :3] )
				if model_name == "deta-swin-large":
								__magic_name__						:						str										=torch.tensor(
								    [[-7.6_3_0_8, -2.8_4_8_5, -5.3_7_3_7], [-7.2_0_3_7, -4.5_5_0_5, -4.8_0_2_7], [-7.2_9_4_3, -4.2_6_1_1, -4.6_6_1_7]] )
								__magic_name__						:						Dict										=torch.tensor([[0.4_9_8_7, 0.4_9_6_9, 0.9_9_9_9], [0.2_5_4_9, 0.5_4_9_8, 0.4_8_0_5], [0.5_4_9_8, 0.2_7_5_7, 0.0_5_6_9]] )
				elif model_name == "deta-swin-large-o365":
								__magic_name__						:						List[Any]										=torch.tensor(
								    [[-8.0_1_2_2, -3.5_7_2_0, -4.9_7_1_7], [-8.1_5_4_7, -3.6_8_8_6, -4.6_3_8_9], [-7.6_6_1_0, -3.6_1_9_4, -5.0_1_3_4]] )
								__magic_name__						:						Optional[Any]										=torch.tensor([[0.2_5_2_3, 0.5_5_4_9, 0.4_8_8_1], [0.7_7_1_5, 0.4_1_4_9, 0.4_6_0_1], [0.5_5_0_3, 0.2_7_5_3, 0.0_5_7_5]] )
				assert torch.allclose(outputs.logits[0, :3, :3]						,  expected_logits.to(lowerCamelCase )						,  atol=1E-4 )
				assert torch.allclose(outputs.pred_boxes[0, :3, :3]						,  expected_boxes.to(lowerCamelCase )						,  atol=1E-4 )
				print("""Everything ok!""" )

				if pytorch_dump_folder_path:
								# Save model and processor
								logger.info(F"Saving PyTorch model and processor to {pytorch_dump_folder_path}..." )
								Path(lowerCamelCase ).mkdir(exist_ok=lowerCamelCase )
								model.save_pretrained(lowerCamelCase )
								processor.save_pretrained(lowerCamelCase )

				# Push to hub
				if push_to_hub:
								print("""Pushing model and processor to hub...""" )
								model.push_to_hub(F"jozhang97/{model_name}" )
								processor.push_to_hub(F"jozhang97/{model_name}" )


if __name__ == "__main__":
							UpperCAmelCase_		:					Optional[Any]          =  argparse.ArgumentParser()

							parser.add_argument(
							    "--model_name",
							    type=str,
							    default="deta-swin-large",
							    choices=["deta-swin-large", "deta-swin-large-o365"],
							    help="Name of the model you'd like to convert.",
							)
							parser.add_argument(
							    "--pytorch_dump_folder_path",
							    default=None,
							    type=str,
							    help="Path to the folder to output PyTorch model.",
							)
							parser.add_argument(
							    "--push_to_hub", action="store_true", help="Whether or not to push the converted model to the 🤗 hub."
							)
							UpperCAmelCase_		:					str          =  parser.parse_args()
							convert_deta_checkpoint(args.model_name, args.pytorch_dump_folder_path, args.push_to_hub)










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




def 		lowerCAmelCase_ (						lowerCamelCase						,  lowerCamelCase						,  lowerCamelCase						,  lowerCamelCase ):
				__magic_name__						:						Union[str, Any]										=sum(a_i[j] for j in range(lowerCamelCase						,  len(lowerCamelCase ) ) )
				__magic_name__						:						Any										=sum(a_i[j] * base[j] for j in range(min(len(lowerCamelCase )						,  lowerCamelCase ) ) )

				__magic_name__					,			__magic_name__						:						Tuple										=0, 0
				__magic_name__						:						Optional[Any]										=n - i

				__magic_name__						:						Union[str, Any]										=memo.get(lowerCamelCase )

				if sub_memo is not None:
								__magic_name__						:						int										=sub_memo.get(lowerCamelCase )

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

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

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

				__magic_name__						:						Tuple										=sub_memo[c]

				# keep jumps sorted by # of terms skipped
				__magic_name__						:						List[Any]										=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						,  lowerCamelCase						,  lowerCamelCase						,  lowerCamelCase ):
				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)
				__magic_name__						:						Tuple										=i
				__magic_name__					,			__magic_name__					,			__magic_name__						:						Tuple										=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
								__magic_name__						:						Optional[Any]										=ds_c + ds_b
								diff += addend
								__magic_name__						:						str										=0
								for j in range(lowerCamelCase ):
												__magic_name__						:						int										=a_i[j] + addend
												__magic_name__					,			__magic_name__						:						Any										=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						,  lowerCamelCase						,  lowerCamelCase ):
				for j in range(lowerCamelCase						,  len(lowerCamelCase ) ):
								__magic_name__						:						Tuple										=digits[j] + addend
								if s >= 10:
												__magic_name__					,			__magic_name__						:						int										=divmod(lowerCamelCase						,  10 )
												__magic_name__						:						int										=addend // 10 + quotient
								else:
												__magic_name__						:						Dict										=s
												__magic_name__						:						Any										=addend // 10

								if addend == 0:
												break

				while addend > 0:
								__magic_name__					,			__magic_name__						:						Union[str, Any]										=divmod(lowerCamelCase						,  10 )
								digits.append(lowerCamelCase )




def 		lowerCAmelCase_ (						lowerCamelCase = 10**15 ):
				__magic_name__						:						List[str]										=[1]
				__magic_name__						:						str										=1
				__magic_name__						:						str										=0
				while True:
								__magic_name__					,			__magic_name__						:						List[str]										=next_term(lowerCamelCase						,  20						,  i + dn						,  lowerCamelCase )
								dn += terms_jumped
								if dn == n - i:
												break

				__magic_name__						:						int										=0
				for j in range(len(lowerCamelCase ) ):
								a_n += digits[j] * 10**j
				return a_n


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




