






import gc
import os
import tempfile
import unittest

import torch
import torch.nn as nn
import torch.nn.functional as F
from transformers import CLIPTextConfig, CLIPTextModel, CLIPTokenizer

from diffusers import AutoencoderKL, DDIMScheduler, StableDiffusionPipeline, UNetaDConditionModel
from diffusers.loaders import AttnProcsLayers, LoraLoaderMixin
from diffusers.models.attention_processor import (
    Attention,
    AttnProcessor,
    AttnProcessor2_0,
    LoRAAttnProcessor,
    LoRAAttnProcessor2_0,
    LoRAXFormersAttnProcessor,
    XFormersAttnProcessor,
)
from diffusers.utils import TEXT_ENCODER_ATTN_MODULE, floats_tensor, torch_device




def   lowercase__   (  __snake_case					:							nn.Module						):


					'''simple docstring'''


					UpperCAmelCase_					:   str   =		{}
					for name in unet.attn_processors.keys():
										UpperCAmelCase_					:   List[Any]   =		None if name.endswith('attn1.processor'						) else unet.config.cross_attention_dim
										if name.startswith('mid_block'						):
															UpperCAmelCase_					:   List[Any]   =		unet.config.block_out_channels[-1]
										elif name.startswith('up_blocks'						):
															UpperCAmelCase_					:   Union[str, Any]   =		int(name[len('up_blocks.'						)]						)
															UpperCAmelCase_					:   Optional[Any]   =		list(reversed(unet.config.block_out_channels						)						)[block_id]
										elif name.startswith('down_blocks'						):
															UpperCAmelCase_					:   int   =		int(name[len('down_blocks.'						)]						)
															UpperCAmelCase_					:   List[str]   =		unet.config.block_out_channels[block_id]
										UpperCAmelCase_					:   Optional[int]   =		(
										    LoRAAttnProcessor2_0 if hasattr(__snake_case  , 'scaled_dot_product_attention'						) else LoRAAttnProcessor
										)
										UpperCAmelCase_					:   int   =		lora_attn_processor_class(
										    hidden_size=__snake_case  , cross_attention_dim=__snake_case						)
					UpperCAmelCase_					:   Dict   =		AttnProcsLayers(__snake_case						)
					return lora_attn_procs, unet_lora_layers




def   lowercase__   (  __snake_case					:							nn.Module						):


					'''simple docstring'''


					UpperCAmelCase_					:   Optional[int]   =		{}
					UpperCAmelCase_					:   Optional[int]   =		(
					    LoRAAttnProcessor2_0 if hasattr(__snake_case  , 'scaled_dot_product_attention'						) else LoRAAttnProcessor
					)
					for name, module in text_encoder.named_modules():
										if name.endswith(__snake_case						):
															UpperCAmelCase_					:   int   =		lora_attn_processor_class(
															    hidden_size=module.out_proj.out_features  , cross_attention_dim=__snake_case						)
					return text_lora_attn_procs




def   lowercase__   (  __snake_case					:							nn.Module						):


					'''simple docstring'''


					UpperCAmelCase_					:   List[str]   =		create_text_encoder_lora_attn_procs(__snake_case						)
					UpperCAmelCase_					:   Optional[int]   =		AttnProcsLayers(__snake_case						)
					return text_encoder_lora_layers




def   lowercase__   (  __snake_case					:							List[Any]  , __snake_case					:							int=False						):


					'''simple docstring'''


					for _, attn_proc in text_lora_attn_procs.items():
										# set up.weights
										for layer_name, layer_module in attn_proc.named_modules():
															if layer_name.endswith('_lora'						):
																				UpperCAmelCase_					:   Optional[Any]   =		(
																				    torch.randn_like(layer_module.up.weight						)
																				    if randn_weight
																				    else torch.zeros_like(layer_module.up.weight						)
																				)
																				UpperCAmelCase_					:   Union[str, Any]   =		torch.nn.Parameter(__snake_case						)






class 						lowerCamelCase   (unittest.TestCase    ):







		'''simple docstring'''



		def       __UpperCAmelCase    (							self     )			->							List[Any]:
							torch.manual_seed(0     )
							UpperCAmelCase_					:   Tuple   =		UNetaDConditionModel(
							    block_out_channels=(3_2, 6_4)       ,	layers_per_block=2       ,	sample_size=3_2       ,	in_channels=4       ,	out_channels=4       ,	down_block_types=('DownBlock2D', 'CrossAttnDownBlock2D')       ,	up_block_types=('CrossAttnUpBlock2D', 'UpBlock2D')       ,	cross_attention_dim=3_2       ,	)
							UpperCAmelCase_					:   Dict   =		DDIMScheduler(
							    beta_start=0.0_00_85       ,	beta_end=0.0_12       ,	beta_schedule='scaled_linear'       ,	clip_sample=_UpperCamelCase       ,	set_alpha_to_one=_UpperCamelCase       ,	steps_offset=1       ,	)
							torch.manual_seed(0     )
							UpperCAmelCase_					:   List[Any]   =		AutoencoderKL(
							    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=4       ,	)
							UpperCAmelCase_					:   Optional[int]   =		CLIPTextConfig(
							    bos_token_id=0       ,	eos_token_id=2       ,	hidden_size=3_2       ,	intermediate_size=3_7       ,	layer_norm_eps=1E-05       ,	num_attention_heads=4       ,	num_hidden_layers=5       ,	pad_token_id=1       ,	vocab_size=1_0_0_0       ,	)
							UpperCAmelCase_					:   Dict   =		CLIPTextModel(_UpperCamelCase     )
							UpperCAmelCase_					:   List[Any]   =		CLIPTokenizer.from_pretrained('hf-internal-testing/tiny-random-clip'     )

							UpperCAmelCase_ ,						UpperCAmelCase_					:   int   =		create_unet_lora_layers(_UpperCamelCase     )
							UpperCAmelCase_					:   List[str]   =		create_text_encoder_lora_layers(_UpperCamelCase     )

							UpperCAmelCase_					:   int   =		{
							    'unet': unet,
							    'scheduler': scheduler,
							    'vae': vae,
							    'text_encoder': text_encoder,
							    'tokenizer': tokenizer,
							    'safety_checker': None,
							    'feature_extractor': None,
							}
							UpperCAmelCase_					:   str   =		{
							    'unet_lora_layers': unet_lora_layers,
							    'text_encoder_lora_layers': text_encoder_lora_layers,
							    'unet_lora_attn_procs': unet_lora_attn_procs,
							}
							return pipeline_components, lora_components



		def       __UpperCAmelCase    (							self     )			->							List[Any]:
							UpperCAmelCase_					:   Optional[Any]   =		1
							UpperCAmelCase_					:   Any   =		1_0
							UpperCAmelCase_					:   List[str]   =		4
							UpperCAmelCase_					:   Dict   =		(3_2, 3_2)

							UpperCAmelCase_					:   Any   =		torch.manual_seed(0     )
							UpperCAmelCase_					:   List[str]   =		floats_tensor((batch_size, num_channels) + sizes     )
							UpperCAmelCase_					:   Optional[Any]   =		torch.randint(1       ,	_UpperCamelCase       ,	size=(batch_size, sequence_length)       ,	generator=_UpperCamelCase     )

							UpperCAmelCase_					:   List[str]   =		{
							    'prompt': 'A painting of a squirrel eating a burger',
							    'generator': generator,
							    'num_inference_steps': 2,
							    'guidance_scale': 6.0,
							    'output_type': 'numpy',
							}

							return noise, input_ids, pipeline_inputs

							# copied from: https://colab.research.google.com/gist/sayakpaul/df2ef6e1ae6d8c10a49d859883b10860/scratchpad.ipynb



		def       __UpperCAmelCase    (							self     )			->							List[str]:
							UpperCAmelCase_					:   int   =		7_7

							UpperCAmelCase_					:   Any   =		torch.randint(2       ,	5_6       ,	size=(1, max_seq_length)       ,	generator=torch.manual_seed(0     )     )

							UpperCAmelCase_					:   int   =		{}
							UpperCAmelCase_					:   int   =		inputs
							return prepared_inputs



		def       __UpperCAmelCase    (							self       ,	_UpperCamelCase     )			->							Optional[Any]:
							UpperCAmelCase_ ,						UpperCAmelCase_					:   Union[str, Any]   =		self.get_dummy_components()
							LoraLoaderMixin.save_lora_weights(
							    save_directory=_UpperCamelCase       ,	unet_lora_layers=lora_components['unet_lora_layers']       ,	text_encoder_lora_layers=lora_components['text_encoder_lora_layers']       ,	)
							self.assertTrue(os.path.isfile(os.path.join(_UpperCamelCase       ,	'pytorch_lora_weights.bin'     )     )     )



		def       __UpperCAmelCase    (							self     )			->							Dict:
							UpperCAmelCase_ ,						UpperCAmelCase_					:   Tuple   =		self.get_dummy_components()
							UpperCAmelCase_					:   Optional[Any]   =		StableDiffusionPipeline(**_UpperCamelCase     )
							UpperCAmelCase_					:   List[str]   =		sd_pipe.to(_UpperCamelCase     )
							sd_pipe.set_progress_bar_config(disable=_UpperCamelCase     )

							UpperCAmelCase_ ,						UpperCAmelCase_ ,						UpperCAmelCase_					:   int   =		self.get_dummy_inputs()

							UpperCAmelCase_					:   Dict   =		sd_pipe(**_UpperCamelCase     ).images
							UpperCAmelCase_					:   Any   =		original_images[0, -3:, -3:, -1]

							with tempfile.TemporaryDirectory() as tmpdirname:
												LoraLoaderMixin.save_lora_weights(
												    save_directory=_UpperCamelCase       ,	unet_lora_layers=lora_components['unet_lora_layers']       ,	text_encoder_lora_layers=lora_components['text_encoder_lora_layers']       ,	)
												self.assertTrue(os.path.isfile(os.path.join(_UpperCamelCase       ,	'pytorch_lora_weights.bin'     )     )     )
												sd_pipe.load_lora_weights(_UpperCamelCase     )

							UpperCAmelCase_					:   str   =		sd_pipe(**_UpperCamelCase     ).images
							UpperCAmelCase_					:   List[str]   =		lora_images[0, -3:, -3:, -1]

							# Outputs shouldn't match.
							self.assertFalse(torch.allclose(torch.from_numpy(_UpperCamelCase     )       ,	torch.from_numpy(_UpperCamelCase     )     )     )



		def       __UpperCAmelCase    (							self     )			->							Dict:
							UpperCAmelCase_ ,						UpperCAmelCase_					:   Optional[Any]   =		self.get_dummy_components()
							UpperCAmelCase_					:   Tuple   =		StableDiffusionPipeline(**_UpperCamelCase     )
							UpperCAmelCase_					:   int   =		sd_pipe.to(_UpperCamelCase     )
							sd_pipe.set_progress_bar_config(disable=_UpperCamelCase     )

							UpperCAmelCase_ ,						UpperCAmelCase_ ,						UpperCAmelCase_					:   Optional[int]   =		self.get_dummy_inputs()

							UpperCAmelCase_					:   int   =		sd_pipe(**_UpperCamelCase     ).images
							UpperCAmelCase_					:   Any   =		original_images[0, -3:, -3:, -1]

							with tempfile.TemporaryDirectory() as tmpdirname:
												LoraLoaderMixin.save_lora_weights(
												    save_directory=_UpperCamelCase       ,	unet_lora_layers=lora_components['unet_lora_layers']       ,	text_encoder_lora_layers=lora_components['text_encoder_lora_layers']       ,	safe_serialization=_UpperCamelCase       ,	)
												self.assertTrue(os.path.isfile(os.path.join(_UpperCamelCase       ,	'pytorch_lora_weights.safetensors'     )     )     )
												sd_pipe.load_lora_weights(_UpperCamelCase     )

							UpperCAmelCase_					:   List[Any]   =		sd_pipe(**_UpperCamelCase     ).images
							UpperCAmelCase_					:   int   =		lora_images[0, -3:, -3:, -1]

							# Outputs shouldn't match.
							self.assertFalse(torch.allclose(torch.from_numpy(_UpperCamelCase     )       ,	torch.from_numpy(_UpperCamelCase     )     )     )



		def       __UpperCAmelCase    (							self     )			->							Dict:
							UpperCAmelCase_ ,						UpperCAmelCase_					:   Dict   =		self.get_dummy_components()
							UpperCAmelCase_					:   Tuple   =		lora_components['unet_lora_attn_procs']
							UpperCAmelCase_					:   int   =		StableDiffusionPipeline(**_UpperCamelCase     )
							UpperCAmelCase_					:   str   =		sd_pipe.to(_UpperCamelCase     )
							sd_pipe.set_progress_bar_config(disable=_UpperCamelCase     )

							UpperCAmelCase_ ,						UpperCAmelCase_ ,						UpperCAmelCase_					:   List[Any]   =		self.get_dummy_inputs()

							UpperCAmelCase_					:   Optional[Any]   =		sd_pipe(**_UpperCamelCase     ).images
							UpperCAmelCase_					:   Tuple   =		original_images[0, -3:, -3:, -1]

							with tempfile.TemporaryDirectory() as tmpdirname:
												UpperCAmelCase_					:   Union[str, Any]   =		sd_pipe.unet
												unet.set_attn_processor(_UpperCamelCase     )
												unet.save_attn_procs(_UpperCamelCase     )
												self.assertTrue(os.path.isfile(os.path.join(_UpperCamelCase       ,	'pytorch_lora_weights.bin'     )     )     )
												sd_pipe.load_lora_weights(_UpperCamelCase     )

							UpperCAmelCase_					:   int   =		sd_pipe(**_UpperCamelCase     ).images
							UpperCAmelCase_					:   str   =		lora_images[0, -3:, -3:, -1]

							# Outputs shouldn't match.
							self.assertFalse(torch.allclose(torch.from_numpy(_UpperCamelCase     )       ,	torch.from_numpy(_UpperCamelCase     )     )     )



		def       __UpperCAmelCase    (							self     )			->							Any:
							UpperCAmelCase_ ,						UpperCAmelCase_					:   Optional[Any]   =		self.get_dummy_components()
							UpperCAmelCase_					:   Optional[int]   =		StableDiffusionPipeline(**_UpperCamelCase     )

							UpperCAmelCase_					:   List[Any]   =		self.get_dummy_tokens()

							# inference without lora
							UpperCAmelCase_					:   Dict   =		pipe.text_encoder(**_UpperCamelCase     )[0]
							assert outputs_without_lora.shape == (1, 7_7, 3_2)

							# create lora_attn_procs with zeroed out up.weights
							UpperCAmelCase_					:   Union[str, Any]   =		create_text_encoder_lora_attn_procs(pipe.text_encoder     )
							set_lora_up_weights(_UpperCamelCase       ,	randn_weight=_UpperCamelCase     )

							# monkey patch
							pipe._modify_text_encoder(_UpperCamelCase     )

							# verify that it's okay to release the text_attn_procs which holds the LoRAAttnProcessor.
							del text_attn_procs
							gc.collect()

							# inference with lora
							UpperCAmelCase_					:   Optional[Any]   =		pipe.text_encoder(**_UpperCamelCase     )[0]
							assert outputs_with_lora.shape == (1, 7_7, 3_2)

							assert torch.allclose(
							    _UpperCamelCase       ,	_UpperCamelCase     ), "lora_up_weight are all zero, so the lora outputs should be the same to without lora outputs"

							# create lora_attn_procs with randn up.weights
							UpperCAmelCase_					:   Dict   =		create_text_encoder_lora_attn_procs(pipe.text_encoder     )
							set_lora_up_weights(_UpperCamelCase       ,	randn_weight=_UpperCamelCase     )

							# monkey patch
							pipe._modify_text_encoder(_UpperCamelCase     )

							# verify that it's okay to release the text_attn_procs which holds the LoRAAttnProcessor.
							del text_attn_procs
							gc.collect()

							# inference with lora
							UpperCAmelCase_					:   Optional[int]   =		pipe.text_encoder(**_UpperCamelCase     )[0]
							assert outputs_with_lora.shape == (1, 7_7, 3_2)

							assert not torch.allclose(
							    _UpperCamelCase       ,	_UpperCamelCase     ), "lora_up_weight are not zero, so the lora outputs should be different to without lora outputs"



		def       __UpperCAmelCase    (							self     )			->							str:
							UpperCAmelCase_ ,						UpperCAmelCase_					:   Tuple   =		self.get_dummy_components()
							UpperCAmelCase_					:   List[Any]   =		StableDiffusionPipeline(**_UpperCamelCase     )

							UpperCAmelCase_					:   Dict   =		self.get_dummy_tokens()

							# inference without lora
							UpperCAmelCase_					:   List[Any]   =		pipe.text_encoder(**_UpperCamelCase     )[0]
							assert outputs_without_lora.shape == (1, 7_7, 3_2)

							# create lora_attn_procs with randn up.weights
							UpperCAmelCase_					:   List[Any]   =		create_text_encoder_lora_attn_procs(pipe.text_encoder     )
							set_lora_up_weights(_UpperCamelCase       ,	randn_weight=_UpperCamelCase     )

							# monkey patch
							pipe._modify_text_encoder(_UpperCamelCase     )

							# verify that it's okay to release the text_attn_procs which holds the LoRAAttnProcessor.
							del text_attn_procs
							gc.collect()

							# inference with lora
							UpperCAmelCase_					:   List[Any]   =		pipe.text_encoder(**_UpperCamelCase     )[0]
							assert outputs_with_lora.shape == (1, 7_7, 3_2)

							assert not torch.allclose(
							    _UpperCamelCase       ,	_UpperCamelCase     ), "lora outputs should be different to without lora outputs"

							# remove monkey patch
							pipe._remove_text_encoder_monkey_patch()

							# inference with removed lora
							UpperCAmelCase_					:   List[Any]   =		pipe.text_encoder(**_UpperCamelCase     )[0]
							assert outputs_without_lora_removed.shape == (1, 7_7, 3_2)

							assert torch.allclose(
							    _UpperCamelCase       ,	_UpperCamelCase     ), "remove lora monkey patch should restore the original outputs"



		def       __UpperCAmelCase    (							self     )			->							int:
							UpperCAmelCase_ ,						UpperCAmelCase_					:   Optional[Any]   =		self.get_dummy_components()
							UpperCAmelCase_					:   Tuple   =		StableDiffusionPipeline(**_UpperCamelCase     )
							UpperCAmelCase_					:   int   =		sd_pipe.to(_UpperCamelCase     )
							sd_pipe.set_progress_bar_config(disable=_UpperCamelCase     )

							UpperCAmelCase_ ,						UpperCAmelCase_ ,						UpperCAmelCase_					:   int   =		self.get_dummy_inputs()

							with tempfile.TemporaryDirectory() as tmpdirname:
												LoraLoaderMixin.save_lora_weights(
												    save_directory=_UpperCamelCase       ,	unet_lora_layers=lora_components['unet_lora_layers']       ,	text_encoder_lora_layers=lora_components['text_encoder_lora_layers']       ,	)
												self.assertTrue(os.path.isfile(os.path.join(_UpperCamelCase       ,	'pytorch_lora_weights.bin'     )     )     )
												sd_pipe.load_lora_weights(_UpperCamelCase     )

							UpperCAmelCase_					:   Tuple   =		sd_pipe(**_UpperCamelCase     ).images
							UpperCAmelCase_					:   List[Any]   =		lora_images[0, -3:, -3:, -1]

							UpperCAmelCase_					:   Optional[int]   =		sd_pipe(**_UpperCamelCase       ,	cross_attention_kwargs={'scale': 0.5}     ).images
							UpperCAmelCase_					:   Dict   =		lora_images_with_scale[0, -3:, -3:, -1]

							# Outputs shouldn't match.
							self.assertFalse(
							    torch.allclose(torch.from_numpy(_UpperCamelCase     )       ,	torch.from_numpy(_UpperCamelCase     )     )     )



		def       __UpperCAmelCase    (							self     )			->							Any:
							with tempfile.TemporaryDirectory() as tmpdirname:
												self.create_lora_weight_file(_UpperCamelCase     )

												UpperCAmelCase_ ,						UpperCAmelCase_					:   List[Any]   =		self.get_dummy_components()
												UpperCAmelCase_					:   List[Any]   =		StableDiffusionPipeline(**_UpperCamelCase     )
												UpperCAmelCase_					:   List[str]   =		sd_pipe.to(_UpperCamelCase     )
												sd_pipe.set_progress_bar_config(disable=_UpperCamelCase     )

												# check if vanilla attention processors are used
												for _, module in sd_pipe.unet.named_modules():
																	if isinstance(_UpperCamelCase       ,	_UpperCamelCase     ):
																						self.assertIsInstance(module.processor       ,	(AttnProcessor, AttnProcessor2_0)     )

            # load LoRA weight file
												sd_pipe.load_lora_weights(_UpperCamelCase     )

												# check if lora attention processors are used
												for _, module in sd_pipe.unet.named_modules():
																	if isinstance(_UpperCamelCase       ,	_UpperCamelCase     ):
																						UpperCAmelCase_					:   Union[str, Any]   =		(
																						    LoRAAttnProcessor2_0 if hasattr(_UpperCamelCase       ,	'scaled_dot_product_attention'     ) else LoRAAttnProcessor
																						)
																						self.assertIsInstance(module.processor       ,	_UpperCamelCase     )



		@unittest.skipIf(torch_device != 'cuda'       ,	'This test is supposed to run on GPU'     )
		def       __UpperCAmelCase    (							self     )			->							Union[str, Any]:
							with tempfile.TemporaryDirectory() as tmpdirname:
												self.create_lora_weight_file(_UpperCamelCase     )

												UpperCAmelCase_ ,						UpperCAmelCase_					:   str   =		self.get_dummy_components()
												UpperCAmelCase_					:   Tuple   =		StableDiffusionPipeline(**_UpperCamelCase     )
												UpperCAmelCase_					:   List[Any]   =		sd_pipe.to(_UpperCamelCase     )
												sd_pipe.set_progress_bar_config(disable=_UpperCamelCase     )

												# enable XFormers
												sd_pipe.enable_xformers_memory_efficient_attention()

												# check if xFormers attention processors are used
												for _, module in sd_pipe.unet.named_modules():
																	if isinstance(_UpperCamelCase       ,	_UpperCamelCase     ):
																						self.assertIsInstance(module.processor       ,	_UpperCamelCase     )

            # load LoRA weight file
												sd_pipe.load_lora_weights(_UpperCamelCase     )

												# check if lora attention processors are used
												for _, module in sd_pipe.unet.named_modules():
																	if isinstance(_UpperCamelCase       ,	_UpperCamelCase     ):
																						self.assertIsInstance(module.processor       ,	_UpperCamelCase     )



		@unittest.skipIf(torch_device != 'cuda'       ,	'This test is supposed to run on GPU'     )
		def       __UpperCAmelCase    (							self     )			->							List[str]:
							UpperCAmelCase_ ,						UpperCAmelCase_					:   Dict   =		self.get_dummy_components()
							UpperCAmelCase_					:   Tuple   =		StableDiffusionPipeline(**_UpperCamelCase     )
							UpperCAmelCase_					:   Optional[Any]   =		sd_pipe.to(_UpperCamelCase     )
							sd_pipe.set_progress_bar_config(disable=_UpperCamelCase     )

							UpperCAmelCase_ ,						UpperCAmelCase_ ,						UpperCAmelCase_					:   List[Any]   =		self.get_dummy_inputs()

							# enable XFormers
							sd_pipe.enable_xformers_memory_efficient_attention()

							UpperCAmelCase_					:   Union[str, Any]   =		sd_pipe(**_UpperCamelCase     ).images
							UpperCAmelCase_					:   Any   =		original_images[0, -3:, -3:, -1]

							with tempfile.TemporaryDirectory() as tmpdirname:
												LoraLoaderMixin.save_lora_weights(
												    save_directory=_UpperCamelCase       ,	unet_lora_layers=lora_components['unet_lora_layers']       ,	text_encoder_lora_layers=lora_components['text_encoder_lora_layers']       ,	)
												self.assertTrue(os.path.isfile(os.path.join(_UpperCamelCase       ,	'pytorch_lora_weights.bin'     )     )     )
												sd_pipe.load_lora_weights(_UpperCamelCase     )

							UpperCAmelCase_					:   List[str]   =		sd_pipe(**_UpperCamelCase     ).images
							UpperCAmelCase_					:   Optional[Any]   =		lora_images[0, -3:, -3:, -1]

							# Outputs shouldn't match.
							self.assertFalse(torch.allclose(torch.from_numpy(_UpperCamelCase     )       ,	torch.from_numpy(_UpperCamelCase     )     )     )














from __future__ import annotations




def   lowercase__   (  __snake_case					:							Any  , __snake_case					:							int						):


					'''simple docstring'''


					UpperCAmelCase_					:   Optional[int]   =		0
					UpperCAmelCase_					:   Optional[int]   =		len(__snake_case						) - 1
					while left <= right:
										UpperCAmelCase_					:   Optional[Any]   =		(left + right) // 2
										if left == right:
															if sorted_list[middle] < item:
																				UpperCAmelCase_					:   List[Any]   =		middle + 1
															break
										elif sorted_list[middle] < item:
															UpperCAmelCase_					:   Union[str, Any]   =		middle + 1
										else:
															UpperCAmelCase_					:   Tuple   =		middle - 1
					sorted_list.insert(__snake_case  , __snake_case						)
					return sorted_list




def   lowercase__   (  __snake_case					:							Union[str, Any]  , __snake_case					:							int						):


					'''simple docstring'''


					UpperCAmelCase_					:   str   =		[]
					while left and right:
										if left[0][0] < right[0][0]:
															result.append(left.pop(0						)						)
										else:
															result.append(right.pop(0						)						)
					return result + left + right




def   lowercase__   (  __snake_case					:							Dict						):


					'''simple docstring'''


					UpperCAmelCase_					:   str   =		len(__snake_case						)
					if length <= 1:
										return list_ad
					UpperCAmelCase_					:   List[Any]   =		length // 2
					return merge(sortlist_ad(list_ad[:middle]						)  , sortlist_ad(list_ad[middle:]						)						)




def   lowercase__   (  __snake_case					:							list[int]						):


					'''simple docstring'''


					if len(__snake_case						) <= 1:
										return collection
					UpperCAmelCase_					:   Any   =		[]
					UpperCAmelCase_					:   Union[str, Any]   =		False
					for i in range(0  , len(__snake_case						)  , 2						):
										if i == len(__snake_case						) - 1:
															UpperCAmelCase_					:   Tuple   =		True
										else:
															if collection[i] < collection[i + 1]:
																				two_paired_list.append([collection[i], collection[i + 1]]						)
															else:
																				two_paired_list.append([collection[i + 1], collection[i]]						)
					UpperCAmelCase_					:   Union[str, Any]   =		sortlist_ad(__snake_case						)
					UpperCAmelCase_					:   Any   =		[i[0] for i in sorted_list_ad]
					result.append(sorted_list_ad[-1][1]						)
					if has_last_odd_item:
										UpperCAmelCase_					:   Union[str, Any]   =		collection[-1]
										UpperCAmelCase_					:   List[Any]   =		binary_search_insertion(__snake_case  , __snake_case						)
					UpperCAmelCase_					:   Tuple   =		False
					for i in range(len(__snake_case						) - 1						):
										if result[i] == collection[-1] and has_last_odd_item:
															UpperCAmelCase_					:   List[Any]   =		True
										UpperCAmelCase_					:   Optional[int]   =		sorted_list_ad[i][1]
										# If last_odd_item is inserted before the item's index,
										# you should forward index one more.
										if is_last_odd_item_inserted_before_this_index:
															UpperCAmelCase_					:   List[str]   =		result[: i + 2] + binary_search_insertion(result[i + 2 :]  , __snake_case						)
										else:
															UpperCAmelCase_					:   List[Any]   =		result[: i + 1] + binary_search_insertion(result[i + 1 :]  , __snake_case						)

					return result


if __name__ == "__main__":
		__UpperCAmelCase										=		input('Enter numbers separated by a comma:\n').strip()
		__UpperCAmelCase										=		[int(item) for item in user_input.split(',')]
		print(merge_insertion_sort(unsorted))






