






'''simple docstring'''





import argparse
import json

import torch

from diffusers import AutoencoderKL, DDPMPipeline, DDPMScheduler, UNetaDModel, VQModel
def __UpperCAmelCase (			A			:	int	,   A			:	Any=1						)  -> Tuple:
			if n_shave_prefix_segments >= 0:
						return ".".join(path.split('''.'''						)[n_shave_prefix_segments:]						)
			else:
						return ".".join(path.split('''.'''						)[:n_shave_prefix_segments]						)
def __UpperCAmelCase (			A			:	Optional[Any]	,   A			:	List[str]=0						)  -> List[Any]:
			UpperCAmelCase_     :   Union[str, Any]       =   []
			for old_item in old_list:
						UpperCAmelCase_     :   Any       =   old_item
						UpperCAmelCase_     :   str       =   new_item.replace('''block.'''	,   '''resnets.'''						)
						UpperCAmelCase_     :   int       =   new_item.replace('''conv_shorcut'''	,   '''conv1'''						)
						UpperCAmelCase_     :   Union[str, Any]       =   new_item.replace('''in_shortcut'''	,   '''conv_shortcut'''						)
						UpperCAmelCase_     :   Optional[int]       =   new_item.replace('''temb_proj'''	,   '''time_emb_proj'''						)

						UpperCAmelCase_     :   Union[str, Any]       =   shave_segments(A	,   n_shave_prefix_segments=A						)

						mapping.append({'''old''': old_item, '''new''': new_item}						)

			return mapping
def __UpperCAmelCase (			A			:	List[str]	,   A			:	Any=0	,   A			:	List[str]=False						)  -> str:
			UpperCAmelCase_     :   List[str]       =   []
			for old_item in old_list:
						UpperCAmelCase_     :   Dict       =   old_item

						# In `model.mid`, the layer is called `attn`.
						if not in_mid:
									UpperCAmelCase_     :   Optional[Any]       =   new_item.replace('''attn'''	,   '''attentions'''						)
						UpperCAmelCase_     :   List[str]       =   new_item.replace('''.k.'''	,   '''.key.'''						)
						UpperCAmelCase_     :   Optional[int]       =   new_item.replace('''.v.'''	,   '''.value.'''						)
						UpperCAmelCase_     :   Optional[Any]       =   new_item.replace('''.q.'''	,   '''.query.'''						)

						UpperCAmelCase_     :   List[Any]       =   new_item.replace('''proj_out'''	,   '''proj_attn'''						)
						UpperCAmelCase_     :   Union[str, Any]       =   new_item.replace('''norm'''	,   '''group_norm'''						)

						UpperCAmelCase_     :   Dict       =   shave_segments(A	,   n_shave_prefix_segments=A						)
						mapping.append({'''old''': old_item, '''new''': new_item}						)

			return mapping
def __UpperCAmelCase (			A			:	Any	,   A			:	List[str]	,   A			:	Tuple	,   A			:	List[Any]=None	,   A			:	Optional[Any]=None	,   A			:	Optional[Any]=None						)  -> Any:
			assert isinstance(A	,   A						), "Paths should be a list of dicts containing 'old' and 'new' keys."

			if attention_paths_to_split is not None:
						if config is None:
									raise ValueError('''Please specify the config if setting \'attention_paths_to_split\' to \'True\'.'''						)

						for path, path_map in attention_paths_to_split.items():
									UpperCAmelCase_     :   Tuple       =   old_checkpoint[path]
									UpperCAmelCase_     :   Any       =   old_tensor.shape[0] // 3

									UpperCAmelCase_     :   Optional[int]       =   (-1, channels) if len(old_tensor.shape						) == 3 else (-1)

									UpperCAmelCase_     :   Optional[int]       =   old_tensor.shape[0] // config.get('''num_head_channels'''	,   1						) // 3

									UpperCAmelCase_     :   Optional[Any]       =   old_tensor.reshape((num_heads, 3 * channels // num_heads) + old_tensor.shape[1:]						)
									UpperCAmelCase_  ,     UpperCAmelCase_  ,     UpperCAmelCase_     :   List[str]       =   old_tensor.split(channels // num_heads	,   dim=1						)

									UpperCAmelCase_     :   List[str]       =   query.reshape(A						).squeeze()
									UpperCAmelCase_     :   str       =   key.reshape(A						).squeeze()
									UpperCAmelCase_     :   Tuple       =   value.reshape(A						).squeeze()

			for path in paths:
						UpperCAmelCase_     :   Any       =   path['''new''']

						if attention_paths_to_split is not None and new_path in attention_paths_to_split:
									continue

						UpperCAmelCase_     :   Optional[Any]       =   new_path.replace('''down.'''	,   '''down_blocks.'''						)
						UpperCAmelCase_     :   int       =   new_path.replace('''up.'''	,   '''up_blocks.'''						)

						if additional_replacements is not None:
									for replacement in additional_replacements:
												UpperCAmelCase_     :   List[Any]       =   new_path.replace(replacement['''old''']	,   replacement['''new''']						)

						if "attentions" in new_path:
									UpperCAmelCase_     :   Union[str, Any]       =   old_checkpoint[path['''old''']].squeeze()
						else:
									UpperCAmelCase_     :   Union[str, Any]       =   old_checkpoint[path['''old''']]
def __UpperCAmelCase (			A			:	List[str]	,   A			:	Any						)  -> Tuple:
			UpperCAmelCase_     :   str       =   {}

			UpperCAmelCase_     :   List[Any]       =   checkpoint['''temb.dense.0.weight''']
			UpperCAmelCase_     :   int       =   checkpoint['''temb.dense.0.bias''']
			UpperCAmelCase_     :   Any       =   checkpoint['''temb.dense.1.weight''']
			UpperCAmelCase_     :   List[str]       =   checkpoint['''temb.dense.1.bias''']

			UpperCAmelCase_     :   Optional[int]       =   checkpoint['''norm_out.weight''']
			UpperCAmelCase_     :   Union[str, Any]       =   checkpoint['''norm_out.bias''']

			UpperCAmelCase_     :   Any       =   checkpoint['''conv_in.weight''']
			UpperCAmelCase_     :   str       =   checkpoint['''conv_in.bias''']
			UpperCAmelCase_     :   Union[str, Any]       =   checkpoint['''conv_out.weight''']
			UpperCAmelCase_     :   int       =   checkpoint['''conv_out.bias''']

			UpperCAmelCase_     :   Optional[Any]       =   len({'''.'''.join(layer.split('''.'''						)[:2]						) for layer in checkpoint if '''down''' in layer}						)
			UpperCAmelCase_     :   Any       =   {
			    layer_id: [key for key in checkpoint if F"down.{layer_id}" in key] for layer_id in range(A						)
			}

			UpperCAmelCase_     :   str       =   len({'''.'''.join(layer.split('''.'''						)[:2]						) for layer in checkpoint if '''up''' in layer}						)
			UpperCAmelCase_     :   List[str]       =   {layer_id: [key for key in checkpoint if F"up.{layer_id}" in key] for layer_id in range(A						)}

			for i in range(A						):
						UpperCAmelCase_     :   str       =   (i - 1) // (config['''layers_per_block'''] + 1)

						if any('''downsample''' in layer for layer in down_blocks[i]						):
									UpperCAmelCase_     :   Optional[int]       =   checkpoint[
									    F"down.{i}.downsample.op.weight"
									]
									UpperCAmelCase_     :   List[str]       =   checkpoint[F"down.{i}.downsample.op.bias"]
						#            new_checkpoint[f'down_blocks.{i}.downsamplers.0.op.weight'] = checkpoint[f'down.{i}.downsample.conv.weight']
						#            new_checkpoint[f'down_blocks.{i}.downsamplers.0.op.bias'] = checkpoint[f'down.{i}.downsample.conv.bias']

						if any('''block''' in layer for layer in down_blocks[i]						):
									UpperCAmelCase_     :   Optional[Any]       =   len(
									    {'''.'''.join(shave_segments(A	,   2						).split('''.'''						)[:2]						) for layer in down_blocks[i] if '''block''' in layer}						)
									UpperCAmelCase_     :   List[str]       =   {
									    layer_id: [key for key in down_blocks[i] if F"block.{layer_id}" in key]
									    for layer_id in range(A						)
									}

									if num_blocks > 0:
												for j in range(config['''layers_per_block''']						):
															UpperCAmelCase_     :   Union[str, Any]       =   renew_resnet_paths(blocks[j]						)
															assign_to_checkpoint(A	,   A	,   A						)

						if any('''attn''' in layer for layer in down_blocks[i]						):
									UpperCAmelCase_     :   Tuple       =   len(
									    {'''.'''.join(shave_segments(A	,   2						).split('''.'''						)[:2]						) for layer in down_blocks[i] if '''attn''' in layer}						)
									UpperCAmelCase_     :   str       =   {
									    layer_id: [key for key in down_blocks[i] if F"attn.{layer_id}" in key]
									    for layer_id in range(A						)
									}

									if num_attn > 0:
												for j in range(config['''layers_per_block''']						):
															UpperCAmelCase_     :   Optional[Any]       =   renew_attention_paths(attns[j]						)
															assign_to_checkpoint(A	,   A	,   A	,   config=A						)

			UpperCAmelCase_     :   Dict       =   [key for key in checkpoint if '''mid.block_1''' in key]
			UpperCAmelCase_     :   Dict       =   [key for key in checkpoint if '''mid.block_2''' in key]
			UpperCAmelCase_     :   Union[str, Any]       =   [key for key in checkpoint if '''mid.attn_1''' in key]

			# Mid new 2
			UpperCAmelCase_     :   str       =   renew_resnet_paths(A						)
			assign_to_checkpoint(
			    A	,   A	,   A	,   additional_replacements=[{'''old''': '''mid.''', '''new''': '''mid_new_2.'''}, {'''old''': '''block_1''', '''new''': '''resnets.0'''}]	,   )

			UpperCAmelCase_     :   Any       =   renew_resnet_paths(A						)
			assign_to_checkpoint(
			    A	,   A	,   A	,   additional_replacements=[{'''old''': '''mid.''', '''new''': '''mid_new_2.'''}, {'''old''': '''block_2''', '''new''': '''resnets.1'''}]	,   )

			UpperCAmelCase_     :   Optional[int]       =   renew_attention_paths(A	,   in_mid=A						)
			assign_to_checkpoint(
			    A	,   A	,   A	,   additional_replacements=[{'''old''': '''mid.''', '''new''': '''mid_new_2.'''}, {'''old''': '''attn_1''', '''new''': '''attentions.0'''}]	,   )

			for i in range(A						):
						UpperCAmelCase_     :   Dict       =   num_up_blocks - 1 - i

						if any('''upsample''' in layer for layer in up_blocks[i]						):
									UpperCAmelCase_     :   List[Any]       =   checkpoint[
									    F"up.{i}.upsample.conv.weight"
									]
									UpperCAmelCase_     :   Optional[Any]       =   checkpoint[F"up.{i}.upsample.conv.bias"]

						if any('''block''' in layer for layer in up_blocks[i]						):
									UpperCAmelCase_     :   int       =   len(
									    {'''.'''.join(shave_segments(A	,   2						).split('''.'''						)[:2]						) for layer in up_blocks[i] if '''block''' in layer}						)
									UpperCAmelCase_     :   str       =   {
									    layer_id: [key for key in up_blocks[i] if F"block.{layer_id}" in key] for layer_id in range(A						)
									}

									if num_blocks > 0:
												for j in range(config['''layers_per_block'''] + 1						):
															UpperCAmelCase_     :   Optional[Any]       =   {'''old''': F"up_blocks.{i}", '''new''': F"up_blocks.{block_id}"}
															UpperCAmelCase_     :   int       =   renew_resnet_paths(blocks[j]						)
															assign_to_checkpoint(A	,   A	,   A	,   additional_replacements=[replace_indices]						)

						if any('''attn''' in layer for layer in up_blocks[i]						):
									UpperCAmelCase_     :   Optional[Any]       =   len(
									    {'''.'''.join(shave_segments(A	,   2						).split('''.'''						)[:2]						) for layer in up_blocks[i] if '''attn''' in layer}						)
									UpperCAmelCase_     :   int       =   {
									    layer_id: [key for key in up_blocks[i] if F"attn.{layer_id}" in key] for layer_id in range(A						)
									}

									if num_attn > 0:
												for j in range(config['''layers_per_block'''] + 1						):
															UpperCAmelCase_     :   List[Any]       =   {'''old''': F"up_blocks.{i}", '''new''': F"up_blocks.{block_id}"}
															UpperCAmelCase_     :   int       =   renew_attention_paths(attns[j]						)
															assign_to_checkpoint(A	,   A	,   A	,   additional_replacements=[replace_indices]						)

			UpperCAmelCase_     :   List[str]       =   {k.replace('''mid_new_2'''	,   '''mid_block'''						): v for k, v in new_checkpoint.items()}
			return new_checkpoint
def __UpperCAmelCase (			A			:	int	,   A			:	List[Any]						)  -> Any:
			UpperCAmelCase_     :   int       =   {}

			UpperCAmelCase_     :   Optional[Any]       =   checkpoint['''encoder.norm_out.weight''']
			UpperCAmelCase_     :   Optional[int]       =   checkpoint['''encoder.norm_out.bias''']

			UpperCAmelCase_     :   str       =   checkpoint['''encoder.conv_in.weight''']
			UpperCAmelCase_     :   Optional[Any]       =   checkpoint['''encoder.conv_in.bias''']
			UpperCAmelCase_     :   str       =   checkpoint['''encoder.conv_out.weight''']
			UpperCAmelCase_     :   Tuple       =   checkpoint['''encoder.conv_out.bias''']

			UpperCAmelCase_     :   str       =   checkpoint['''decoder.norm_out.weight''']
			UpperCAmelCase_     :   Optional[int]       =   checkpoint['''decoder.norm_out.bias''']

			UpperCAmelCase_     :   List[Any]       =   checkpoint['''decoder.conv_in.weight''']
			UpperCAmelCase_     :   int       =   checkpoint['''decoder.conv_in.bias''']
			UpperCAmelCase_     :   List[Any]       =   checkpoint['''decoder.conv_out.weight''']
			UpperCAmelCase_     :   int       =   checkpoint['''decoder.conv_out.bias''']

			UpperCAmelCase_     :   Optional[Any]       =   len({'''.'''.join(layer.split('''.'''						)[:3]						) for layer in checkpoint if '''down''' in layer}						)
			UpperCAmelCase_     :   List[str]       =   {
			    layer_id: [key for key in checkpoint if F"down.{layer_id}" in key] for layer_id in range(A						)
			}

			UpperCAmelCase_     :   Tuple       =   len({'''.'''.join(layer.split('''.'''						)[:3]						) for layer in checkpoint if '''up''' in layer}						)
			UpperCAmelCase_     :   Union[str, Any]       =   {layer_id: [key for key in checkpoint if F"up.{layer_id}" in key] for layer_id in range(A						)}

			for i in range(A						):
						UpperCAmelCase_     :   Tuple       =   (i - 1) // (config['''layers_per_block'''] + 1)

						if any('''downsample''' in layer for layer in down_blocks[i]						):
									UpperCAmelCase_     :   Optional[Any]       =   checkpoint[
									    F"encoder.down.{i}.downsample.conv.weight"
									]
									UpperCAmelCase_     :   str       =   checkpoint[
									    F"encoder.down.{i}.downsample.conv.bias"
									]

						if any('''block''' in layer for layer in down_blocks[i]						):
									UpperCAmelCase_     :   Union[str, Any]       =   len(
									    {'''.'''.join(shave_segments(A	,   3						).split('''.'''						)[:3]						) for layer in down_blocks[i] if '''block''' in layer}						)
									UpperCAmelCase_     :   Dict       =   {
									    layer_id: [key for key in down_blocks[i] if F"block.{layer_id}" in key]
									    for layer_id in range(A						)
									}

									if num_blocks > 0:
												for j in range(config['''layers_per_block''']						):
															UpperCAmelCase_     :   Optional[Any]       =   renew_resnet_paths(blocks[j]						)
															assign_to_checkpoint(A	,   A	,   A						)

						if any('''attn''' in layer for layer in down_blocks[i]						):
									UpperCAmelCase_     :   Any       =   len(
									    {'''.'''.join(shave_segments(A	,   3						).split('''.'''						)[:3]						) for layer in down_blocks[i] if '''attn''' in layer}						)
									UpperCAmelCase_     :   Optional[int]       =   {
									    layer_id: [key for key in down_blocks[i] if F"attn.{layer_id}" in key]
									    for layer_id in range(A						)
									}

									if num_attn > 0:
												for j in range(config['''layers_per_block''']						):
															UpperCAmelCase_     :   Optional[Any]       =   renew_attention_paths(attns[j]						)
															assign_to_checkpoint(A	,   A	,   A	,   config=A						)

			UpperCAmelCase_     :   int       =   [key for key in checkpoint if '''mid.block_1''' in key]
			UpperCAmelCase_     :   Tuple       =   [key for key in checkpoint if '''mid.block_2''' in key]
			UpperCAmelCase_     :   List[Any]       =   [key for key in checkpoint if '''mid.attn_1''' in key]

			# Mid new 2
			UpperCAmelCase_     :   Optional[Any]       =   renew_resnet_paths(A						)
			assign_to_checkpoint(
			    A	,   A	,   A	,   additional_replacements=[{'''old''': '''mid.''', '''new''': '''mid_new_2.'''}, {'''old''': '''block_1''', '''new''': '''resnets.0'''}]	,   )

			UpperCAmelCase_     :   List[str]       =   renew_resnet_paths(A						)
			assign_to_checkpoint(
			    A	,   A	,   A	,   additional_replacements=[{'''old''': '''mid.''', '''new''': '''mid_new_2.'''}, {'''old''': '''block_2''', '''new''': '''resnets.1'''}]	,   )

			UpperCAmelCase_     :   Optional[int]       =   renew_attention_paths(A	,   in_mid=A						)
			assign_to_checkpoint(
			    A	,   A	,   A	,   additional_replacements=[{'''old''': '''mid.''', '''new''': '''mid_new_2.'''}, {'''old''': '''attn_1''', '''new''': '''attentions.0'''}]	,   )

			for i in range(A						):
						UpperCAmelCase_     :   Tuple       =   num_up_blocks - 1 - i

						if any('''upsample''' in layer for layer in up_blocks[i]						):
									UpperCAmelCase_     :   Dict       =   checkpoint[
									    F"decoder.up.{i}.upsample.conv.weight"
									]
									UpperCAmelCase_     :   int       =   checkpoint[
									    F"decoder.up.{i}.upsample.conv.bias"
									]

						if any('''block''' in layer for layer in up_blocks[i]						):
									UpperCAmelCase_     :   List[Any]       =   len(
									    {'''.'''.join(shave_segments(A	,   3						).split('''.'''						)[:3]						) for layer in up_blocks[i] if '''block''' in layer}						)
									UpperCAmelCase_     :   Dict       =   {
									    layer_id: [key for key in up_blocks[i] if F"block.{layer_id}" in key] for layer_id in range(A						)
									}

									if num_blocks > 0:
												for j in range(config['''layers_per_block'''] + 1						):
															UpperCAmelCase_     :   Optional[Any]       =   {'''old''': F"up_blocks.{i}", '''new''': F"up_blocks.{block_id}"}
															UpperCAmelCase_     :   Tuple       =   renew_resnet_paths(blocks[j]						)
															assign_to_checkpoint(A	,   A	,   A	,   additional_replacements=[replace_indices]						)

						if any('''attn''' in layer for layer in up_blocks[i]						):
									UpperCAmelCase_     :   Dict       =   len(
									    {'''.'''.join(shave_segments(A	,   3						).split('''.'''						)[:3]						) for layer in up_blocks[i] if '''attn''' in layer}						)
									UpperCAmelCase_     :   Tuple       =   {
									    layer_id: [key for key in up_blocks[i] if F"attn.{layer_id}" in key] for layer_id in range(A						)
									}

									if num_attn > 0:
												for j in range(config['''layers_per_block'''] + 1						):
															UpperCAmelCase_     :   Any       =   {'''old''': F"up_blocks.{i}", '''new''': F"up_blocks.{block_id}"}
															UpperCAmelCase_     :   Tuple       =   renew_attention_paths(attns[j]						)
															assign_to_checkpoint(A	,   A	,   A	,   additional_replacements=[replace_indices]						)

			UpperCAmelCase_     :   Optional[int]       =   {k.replace('''mid_new_2'''	,   '''mid_block'''						): v for k, v in new_checkpoint.items()}
			UpperCAmelCase_     :   List[str]       =   checkpoint['''quant_conv.weight''']
			UpperCAmelCase_     :   Tuple       =   checkpoint['''quant_conv.bias''']
			if "quantize.embedding.weight" in checkpoint:
						UpperCAmelCase_     :   int       =   checkpoint['''quantize.embedding.weight''']
			UpperCAmelCase_     :   Optional[int]       =   checkpoint['''post_quant_conv.weight''']
			UpperCAmelCase_     :   int       =   checkpoint['''post_quant_conv.bias''']

			return new_checkpoint


if __name__ == "__main__":
						_UpperCamelCase		:		Tuple								=			argparse.ArgumentParser()

						parser.add_argument(
						    '--checkpoint_path', default=None, type=str, required=True, help='Path to the checkpoint to convert.'
						)

						parser.add_argument(
						    '--config_file',
						    default=None,
						    type=str,
						    required=True,
						    help='The config json file corresponding to the architecture.',
						)

						parser.add_argument('--dump_path', default=None, type=str, required=True, help='Path to the output model.')

						_UpperCamelCase		:		List[str]								=			parser.parse_args()
						_UpperCamelCase		:		List[Any]								=			torch.load(args.checkpoint_path)

						with open(args.config_file) as f:
												_UpperCamelCase		:		str								=			json.loads(f.read())

						# unet case
						_UpperCamelCase		:		List[Any]								=			{key.split('.')[0] for key in checkpoint.keys()}
						if "encoder" in key_prefix_set and "decoder" in key_prefix_set:
												_UpperCamelCase		:		Optional[int]								=			convert_vq_autoenc_checkpoint(checkpoint, config)
						else:
												_UpperCamelCase		:		str								=			convert_ddpm_checkpoint(checkpoint, config)

						if "ddpm" in config:
												del config["ddpm"]

						if config["_class_name"] == "VQModel":
												_UpperCamelCase		:		Dict								=			VQModel(**config)
												model.load_state_dict(converted_checkpoint)
												model.save_pretrained(args.dump_path)
						elif config["_class_name"] == "AutoencoderKL":
												_UpperCamelCase		:		Optional[int]								=			AutoencoderKL(**config)
												model.load_state_dict(converted_checkpoint)
												model.save_pretrained(args.dump_path)
						else:
												_UpperCamelCase		:		Optional[Any]								=			UNetaDModel(**config)
												model.load_state_dict(converted_checkpoint)

												_UpperCamelCase		:		List[str]								=			DDPMScheduler.from_config('/'.join(args.checkpoint_path.split('/')[:-1]))

												_UpperCamelCase		:		Optional[Any]								=			DDPMPipeline(unet=model, scheduler=scheduler)
												pipe.save_pretrained(args.dump_path)










'''simple docstring'''





from __future__ import annotations

from collections import deque
from enum import Enum
from math import atana, degrees
from sys import maxsize


class 				snake_case__     (			UpperCamelCase):
					a_       =			1
					a_       =			2
					a_       =			3




					def __repr__(       self       :						str     )  ->    Optional[int]:
								return F"{self.__class__.__name__}.{self.name}"






def __UpperCAmelCase (			A			:	tuple[int, int]	,   A			:	int	,   A			:	int						)  -> float:
			UpperCAmelCase_  ,     UpperCAmelCase_     :   Any       =   point
			return degrees(atana(y - miny	,   x - minx						)						)
def __UpperCAmelCase (			A			:	tuple[int, int]	,   A			:	tuple[int, int]	,   A			:	tuple[int, int]						)  -> Direction:
			UpperCAmelCase_  ,     UpperCAmelCase_     :   Tuple       =   starting
			UpperCAmelCase_  ,     UpperCAmelCase_     :   Optional[Any]       =   via
			UpperCAmelCase_  ,     UpperCAmelCase_     :   Optional[int]       =   target
			UpperCAmelCase_     :   Optional[int]       =   degrees(atana(ya - ya	,   xa - xa						)						)
			via_angle %= 3_6_0
			UpperCAmelCase_     :   Dict       =   degrees(atana(ya - ya	,   xa - xa						)						)
			target_angle %= 3_6_0
			# t-
			#  \ \
			#   \ v
			#    \|
			#     s
			# via_angle is always lower than target_angle, if direction is left.
			# If they are same, it means they are on a same line of convex hull.
			if target_angle > via_angle:
						return Direction.left
			elif target_angle == via_angle:
						return Direction.straight
			else:
						return Direction.right







def __UpperCAmelCase (			A			:	list[tuple[int, int]]						)  -> list[tuple[int, int]]:

			if len(A						) <= 2:
						# There is no convex hull
						raise ValueError('''graham_scan: argument must contain more than 3 points.'''						)
			if len(A						) == 3:
						return points
			# find the lowest and the most left point
			UpperCAmelCase_     :   List[str]       =   0
			UpperCAmelCase_  ,     UpperCAmelCase_     :   List[Any]       =   maxsize, maxsize
			for i, point in enumerate(A						):
						UpperCAmelCase_     :   str       =   point[0]
						UpperCAmelCase_     :   List[Any]       =   point[1]
						if y < miny:
									UpperCAmelCase_     :   int       =   y
									UpperCAmelCase_     :   Dict       =   x
									UpperCAmelCase_     :   Any       =   i
						if y == miny and x < minx:
									UpperCAmelCase_     :   str       =   x
									UpperCAmelCase_     :   Optional[int]       =   i

    # remove the lowest and the most left point from points for preparing for sort
			points.pop(A						)

			UpperCAmelCase_     :   Optional[Any]       =   sorted(A	,   key=lambda A						: angle_comparer(A	,   A	,   A						)						)
			# This insert actually costs complexity,
			# and you should instead add (minx, miny) into stack later.
			# I'm using insert just for easy understanding.
			sorted_points.insert(0	,   (minx, miny)						)

			UpperCAmelCase_     :   deque[tuple[int, int]]       =   deque()
			stack.append(sorted_points[0]						)
			stack.append(sorted_points[1]						)
			stack.append(sorted_points[2]						)
			# In any ways, the first 3 points line are towards left.
			# Because we sort them the angle from minx, miny.
			UpperCAmelCase_     :   Any       =   Direction.left

			for i in range(3	,   len(A						)						):
						while True:
									UpperCAmelCase_     :   Any       =   stack[-2]
									UpperCAmelCase_     :   List[Any]       =   stack[-1]
									UpperCAmelCase_     :   Any       =   sorted_points[i]
									UpperCAmelCase_     :   Tuple       =   check_direction(A	,   A	,   A						)

									if next_direction == Direction.left:
												UpperCAmelCase_     :   Optional[Any]       =   Direction.left
												break
									if next_direction == Direction.straight:
												if current_direction == Direction.left:
															# We keep current_direction as left.
															# Because if the straight line keeps as straight,
															# we want to know if this straight line is towards left.
															break
												elif current_direction == Direction.right:
															# If the straight line is towards right,
															# every previous points on those straigh line is not convex hull.
															stack.pop()
									if next_direction == Direction.right:
												stack.pop()
						stack.append(sorted_points[i]						)
			return list(A						)


