






'''simple docstring'''





import gc
import random
import tempfile
import unittest

import numpy as np
import torch
from transformers import CLIPTextConfig, CLIPTextModel, CLIPTokenizer

from diffusers import AutoencoderKL, DDIMScheduler, LMSDiscreteScheduler, PNDMScheduler, UNetaDConditionModel
from diffusers.pipelines.semantic_stable_diffusion import SemanticStableDiffusionPipeline as StableDiffusionPipeline
from diffusers.utils import floats_tensor, nightly, torch_device
from diffusers.utils.testing_utils import enable_full_determinism, require_torch_gpu


enable_full_determinism()


class 				snake_case__     (			unittest.TestCase):




					def 						A     (       self       :						Optional[int]     )  ->    Dict:
								super().tearDown()
								gc.collect()
								torch.cuda.empty_cache()




					@property
					def 						A     (       self       :						List[str]     )  ->    Tuple:
								UpperCAmelCase_     :   int       =   1
								UpperCAmelCase_     :   int       =   3
								UpperCAmelCase_     :   int       =   (32, 32)

								UpperCAmelCase_     :   str       =   floats_tensor((batch_size, num_channels) + sizes							,				rng=random.Random(0     )     ).to(_A     )
								return image




					@property
					def 						A     (       self       :						Union[str, Any]     )  ->    int:
								torch.manual_seed(0     )
								UpperCAmelCase_     :   List[str]       =   UNetaDConditionModel(
								    block_out_channels=(32, 64)							,				layers_per_block=2							,				sample_size=32							,				in_channels=4							,				out_channels=4							,				down_block_types=('''DownBlock2D''', '''CrossAttnDownBlock2D''')							,				up_block_types=('''CrossAttnUpBlock2D''', '''UpBlock2D''')							,				cross_attention_dim=32							,				)
								return model




					@property
					def 						A     (       self       :						Optional[int]     )  ->    Optional[Any]:
								torch.manual_seed(0     )
								UpperCAmelCase_     :   str       =   AutoencoderKL(
								    block_out_channels=[32, 64]							,				in_channels=3							,				out_channels=3							,				down_block_types=['''DownEncoderBlock2D''', '''DownEncoderBlock2D''']							,				up_block_types=['''UpDecoderBlock2D''', '''UpDecoderBlock2D''']							,				latent_channels=4							,				)
								return model




					@property
					def 						A     (       self       :						int     )  ->    Optional[Any]:
								torch.manual_seed(0     )
								UpperCAmelCase_     :   Any       =   CLIPTextConfig(
								    bos_token_id=0							,				eos_token_id=2							,				hidden_size=32							,				intermediate_size=37							,				layer_norm_eps=1e-05							,				num_attention_heads=4							,				num_hidden_layers=5							,				pad_token_id=1							,				vocab_size=10_00							,				)
								return CLIPTextModel(_A     )




					@property
					def 						A     (       self       :						List[Any]     )  ->    Union[str, Any]:



								def extract(*_A       :						Optional[Any]							,				**_A       :						List[str]     ):


											class 				snake_case__     :




																def __init__(       self       :						Optional[Any]     )  ->    Optional[int]:
																			UpperCAmelCase_     :   Dict       =   torch.ones([0]     )





																def 						A     (       self       :						Optional[Any]							,				_A       :						Tuple     )  ->    Optional[Any]:
																			self.pixel_values.to(_A     )
																			return self






											return Out()

								return extract




					def 						A     (       self       :						Union[str, Any]     )  ->    Tuple:
								UpperCAmelCase_     :   int       =   '''cpu'''  # ensure determinism for the device-dependent torch.Generator
								UpperCAmelCase_     :   Optional[int]       =   self.dummy_cond_unet
								UpperCAmelCase_     :   Optional[Any]       =   DDIMScheduler(
								    beta_start=0.00_085							,				beta_end=0.012							,				beta_schedule='''scaled_linear'''							,				clip_sample=_A							,				set_alpha_to_one=_A							,				)

								UpperCAmelCase_     :   Optional[Any]       =   self.dummy_vae
								UpperCAmelCase_     :   Dict       =   self.dummy_text_encoder
								UpperCAmelCase_     :   List[str]       =   CLIPTokenizer.from_pretrained('''hf-internal-testing/tiny-random-clip'''     )

								# make sure here that pndm scheduler skips prk
								UpperCAmelCase_     :   str       =   StableDiffusionPipeline(
								    unet=_A							,				scheduler=_A							,				vae=_A							,				text_encoder=_A							,				tokenizer=_A							,				safety_checker=_A							,				feature_extractor=self.dummy_extractor							,				)
								UpperCAmelCase_     :   Tuple       =   sd_pipe.to(_A     )
								sd_pipe.set_progress_bar_config(disable=_A     )

								UpperCAmelCase_     :   Any       =   '''A painting of a squirrel eating a burger'''

								UpperCAmelCase_     :   List[str]       =   torch.Generator(device=_A     ).manual_seed(0     )
								UpperCAmelCase_     :   List[Any]       =   sd_pipe([prompt]							,				generator=_A							,				guidance_scale=6.0							,				num_inference_steps=2							,				output_type='''np'''     )
								UpperCAmelCase_     :   List[str]       =   output.images

								UpperCAmelCase_     :   Union[str, Any]       =   torch.Generator(device=_A     ).manual_seed(0     )
								UpperCAmelCase_     :   Optional[int]       =   sd_pipe(
								    [prompt]							,				generator=_A							,				guidance_scale=6.0							,				num_inference_steps=2							,				output_type='''np'''							,				return_dict=_A							,				)[0]

								UpperCAmelCase_     :   Dict       =   image[0, -3:, -3:, -1]
								UpperCAmelCase_     :   List[Any]       =   image_from_tuple[0, -3:, -3:, -1]

								assert image.shape == (1, 64, 64, 3)
								UpperCAmelCase_     :   List[str]       =   np.array([0.5_753, 0.6_114, 0.5_001, 0.5_034, 0.5_470, 0.4_729, 0.4_971, 0.4_867, 0.4_867]     )

								assert np.abs(image_slice.flatten() - expected_slice     ).max() < 1e-2
								assert np.abs(image_from_tuple_slice.flatten() - expected_slice     ).max() < 1e-2




					def 						A     (       self       :						str     )  ->    Any:
								UpperCAmelCase_     :   str       =   '''cpu'''  # ensure determinism for the device-dependent torch.Generator
								UpperCAmelCase_     :   Optional[int]       =   self.dummy_cond_unet
								UpperCAmelCase_     :   int       =   PNDMScheduler(skip_prk_steps=_A     )
								UpperCAmelCase_     :   Any       =   self.dummy_vae
								UpperCAmelCase_     :   str       =   self.dummy_text_encoder
								UpperCAmelCase_     :   List[Any]       =   CLIPTokenizer.from_pretrained('''hf-internal-testing/tiny-random-clip'''     )

								# make sure here that pndm scheduler skips prk
								UpperCAmelCase_     :   Optional[Any]       =   StableDiffusionPipeline(
								    unet=_A							,				scheduler=_A							,				vae=_A							,				text_encoder=_A							,				tokenizer=_A							,				safety_checker=_A							,				feature_extractor=self.dummy_extractor							,				)
								UpperCAmelCase_     :   Union[str, Any]       =   sd_pipe.to(_A     )
								sd_pipe.set_progress_bar_config(disable=_A     )

								UpperCAmelCase_     :   str       =   '''A painting of a squirrel eating a burger'''
								UpperCAmelCase_     :   Any       =   torch.Generator(device=_A     ).manual_seed(0     )
								UpperCAmelCase_     :   Optional[int]       =   sd_pipe([prompt]							,				generator=_A							,				guidance_scale=6.0							,				num_inference_steps=2							,				output_type='''np'''     )

								UpperCAmelCase_     :   Optional[int]       =   output.images

								UpperCAmelCase_     :   Dict       =   torch.Generator(device=_A     ).manual_seed(0     )
								UpperCAmelCase_     :   List[str]       =   sd_pipe(
								    [prompt]							,				generator=_A							,				guidance_scale=6.0							,				num_inference_steps=2							,				output_type='''np'''							,				return_dict=_A							,				)[0]

								UpperCAmelCase_     :   Union[str, Any]       =   image[0, -3:, -3:, -1]
								UpperCAmelCase_     :   List[Any]       =   image_from_tuple[0, -3:, -3:, -1]

								assert image.shape == (1, 64, 64, 3)
								UpperCAmelCase_     :   List[str]       =   np.array([0.5_122, 0.5_712, 0.4_825, 0.5_053, 0.5_646, 0.4_769, 0.5_179, 0.4_894, 0.4_994]     )

								assert np.abs(image_slice.flatten() - expected_slice     ).max() < 1e-2
								assert np.abs(image_from_tuple_slice.flatten() - expected_slice     ).max() < 1e-2




					def 						A     (       self       :						Union[str, Any]     )  ->    str:
								UpperCAmelCase_     :   str       =   StableDiffusionPipeline.from_pretrained(
								    '''hf-internal-testing/tiny-stable-diffusion-lms-pipe'''							,				safety_checker=_A     )
								assert isinstance(_A							,				_A     )
								assert isinstance(pipe.scheduler							,				_A     )
								assert pipe.safety_checker is None

								UpperCAmelCase_     :   Optional[Any]       =   pipe('''example prompt'''							,				num_inference_steps=2     ).images[0]
								assert image is not None

								# check that there's no error when saving a pipeline with one of the models being None
								with tempfile.TemporaryDirectory() as tmpdirname:
											pipe.save_pretrained(_A     )
											UpperCAmelCase_     :   int       =   StableDiffusionPipeline.from_pretrained(_A     )

								# sanity check that the pipeline still works
								assert pipe.safety_checker is None
								UpperCAmelCase_     :   int       =   pipe('''example prompt'''							,				num_inference_steps=2     ).images[0]
								assert image is not None





					@unittest.skipIf(torch_device != '''cuda'''							,				'''This test requires a GPU'''     )
					def 						A     (       self       :						List[Any]     )  ->    int:
								UpperCAmelCase_     :   Any       =   self.dummy_cond_unet
								UpperCAmelCase_     :   Tuple       =   PNDMScheduler(skip_prk_steps=_A     )
								UpperCAmelCase_     :   Tuple       =   self.dummy_vae
								UpperCAmelCase_     :   Dict       =   self.dummy_text_encoder
								UpperCAmelCase_     :   Union[str, Any]       =   CLIPTokenizer.from_pretrained('''hf-internal-testing/tiny-random-clip'''     )

								# put models in fp16
								UpperCAmelCase_     :   Union[str, Any]       =   unet.half()
								UpperCAmelCase_     :   int       =   vae.half()
								UpperCAmelCase_     :   Dict       =   bert.half()

								# make sure here that pndm scheduler skips prk
								UpperCAmelCase_     :   Any       =   StableDiffusionPipeline(
								    unet=_A							,				scheduler=_A							,				vae=_A							,				text_encoder=_A							,				tokenizer=_A							,				safety_checker=_A							,				feature_extractor=self.dummy_extractor							,				)
								UpperCAmelCase_     :   Dict       =   sd_pipe.to(_A     )
								sd_pipe.set_progress_bar_config(disable=_A     )

								UpperCAmelCase_     :   List[str]       =   '''A painting of a squirrel eating a burger'''
								UpperCAmelCase_     :   int       =   sd_pipe([prompt]							,				num_inference_steps=2							,				output_type='''np'''     ).images

								assert image.shape == (1, 64, 64, 3)






@nightly
@require_torch_gpu
class 				snake_case__     (			unittest.TestCase):




					def 						A     (       self       :						Optional[int]     )  ->    Dict:
								super().tearDown()
								gc.collect()
								torch.cuda.empty_cache()




					def 						A     (       self       :						Optional[Any]     )  ->    Optional[int]:
								UpperCAmelCase_     :   int       =   '''cuda'''
								UpperCAmelCase_     :   Tuple       =   StableDiffusionPipeline.from_pretrained('''runwayml/stable-diffusion-v1-5'''     )
								UpperCAmelCase_     :   Any       =   pipe.to(_A     )
								pipe.set_progress_bar_config(disable=_A     )

								UpperCAmelCase_     :   Dict       =   '''a photo of a cat'''
								UpperCAmelCase_     :   Optional[int]       =   {
								    '''editing_prompt''': ['''sunglasses'''],
								    '''reverse_editing_direction''': [False],
								    '''edit_warmup_steps''': 10,
								    '''edit_guidance_scale''': 6,
								    '''edit_threshold''': 0.95,
								    '''edit_momentum_scale''': 0.5,
								    '''edit_mom_beta''': 0.6,
								}

								UpperCAmelCase_     :   Optional[Any]       =   3
								UpperCAmelCase_     :   List[str]       =   7

								# no sega enabled
								UpperCAmelCase_     :   Tuple       =   torch.Generator(_A     )
								generator.manual_seed(_A     )
								UpperCAmelCase_     :   int       =   pipe(
								    [prompt]							,				generator=_A							,				guidance_scale=_A							,				num_inference_steps=50							,				output_type='''np'''							,				width=5_12							,				height=5_12							,				)

								UpperCAmelCase_     :   Optional[Any]       =   output.images
								UpperCAmelCase_     :   List[Any]       =   image[0, -3:, -3:, -1]
								UpperCAmelCase_     :   List[str]       =   [
								    0.34_673_113,
								    0.38_492_733,
								    0.37_597_352,
								    0.34_086_335,
								    0.35_650_748,
								    0.35_579_205,
								    0.3_384_763,
								    0.34_340_236,
								    0.3_573_271,
								]

								assert image.shape == (1, 5_12, 5_12, 3)

								assert np.abs(image_slice.flatten() - expected_slice     ).max() < 1e-2

								# with sega enabled
								# generator = torch.manual_seed(seed)
								generator.manual_seed(_A     )
								UpperCAmelCase_     :   List[Any]       =   pipe(
								    [prompt]							,				generator=_A							,				guidance_scale=_A							,				num_inference_steps=50							,				output_type='''np'''							,				width=5_12							,				height=5_12							,				**_A							,				)

								UpperCAmelCase_     :   Union[str, Any]       =   output.images
								UpperCAmelCase_     :   Optional[Any]       =   image[0, -3:, -3:, -1]
								UpperCAmelCase_     :   Optional[int]       =   [
								    0.41_887_826,
								    0.37_728_766,
								    0.30_138_272,
								    0.41_416_335,
								    0.41_664_985,
								    0.36_283_392,
								    0.36_191_246,
								    0.43_364_465,
								    0.43_001_732,
								]

								assert image.shape == (1, 5_12, 5_12, 3)

								assert np.abs(image_slice.flatten() - expected_slice     ).max() < 1e-2




					def 						A     (       self       :						str     )  ->    List[str]:
								UpperCAmelCase_     :   Optional[Any]       =   '''cuda'''
								UpperCAmelCase_     :   Optional[Any]       =   StableDiffusionPipeline.from_pretrained('''runwayml/stable-diffusion-v1-5'''     )
								UpperCAmelCase_     :   Union[str, Any]       =   pipe.to(_A     )
								pipe.set_progress_bar_config(disable=_A     )

								UpperCAmelCase_     :   int       =   '''an image of a crowded boulevard, realistic, 4k'''
								UpperCAmelCase_     :   List[str]       =   {
								    '''editing_prompt''': '''crowd, crowded, people''',
								    '''reverse_editing_direction''': True,
								    '''edit_warmup_steps''': 10,
								    '''edit_guidance_scale''': 8.3,
								    '''edit_threshold''': 0.9,
								    '''edit_momentum_scale''': 0.5,
								    '''edit_mom_beta''': 0.6,
								}

								UpperCAmelCase_     :   List[str]       =   9
								UpperCAmelCase_     :   Tuple       =   7

								# no sega enabled
								UpperCAmelCase_     :   List[str]       =   torch.Generator(_A     )
								generator.manual_seed(_A     )
								UpperCAmelCase_     :   str       =   pipe(
								    [prompt]							,				generator=_A							,				guidance_scale=_A							,				num_inference_steps=50							,				output_type='''np'''							,				width=5_12							,				height=5_12							,				)

								UpperCAmelCase_     :   Tuple       =   output.images
								UpperCAmelCase_     :   Optional[int]       =   image[0, -3:, -3:, -1]
								UpperCAmelCase_     :   Dict       =   [
								    0.43_497_998,
								    0.91_814_065,
								    0.7_540_739,
								    0.55_580_205,
								    0.8_467_265,
								    0.5_389_691,
								    0.62_574_506,
								    0.58_897_763,
								    0.50_926_757,
								]

								assert image.shape == (1, 5_12, 5_12, 3)

								assert np.abs(image_slice.flatten() - expected_slice     ).max() < 1e-2

								# with sega enabled
								# generator = torch.manual_seed(seed)
								generator.manual_seed(_A     )
								UpperCAmelCase_     :   Optional[int]       =   pipe(
								    [prompt]							,				generator=_A							,				guidance_scale=_A							,				num_inference_steps=50							,				output_type='''np'''							,				width=5_12							,				height=5_12							,				**_A							,				)

								UpperCAmelCase_     :   Any       =   output.images
								UpperCAmelCase_     :   Union[str, Any]       =   image[0, -3:, -3:, -1]
								UpperCAmelCase_     :   Optional[int]       =   [
								    0.3_089_719,
								    0.30_500_144,
								    0.29_016_042,
								    0.30_630_964,
								    0.325_687,
								    0.29_419_225,
								    0.2_908_091,
								    0.28_723_598,
								    0.27_696_294,
								]

								assert image.shape == (1, 5_12, 5_12, 3)

								assert np.abs(image_slice.flatten() - expected_slice     ).max() < 1e-2




					def 						A     (       self       :						str     )  ->    int:
								UpperCAmelCase_     :   Optional[Any]       =   '''cuda'''
								UpperCAmelCase_     :   Any       =   StableDiffusionPipeline.from_pretrained('''runwayml/stable-diffusion-v1-5'''     )
								UpperCAmelCase_     :   Any       =   pipe.to(_A     )
								pipe.set_progress_bar_config(disable=_A     )

								UpperCAmelCase_     :   Optional[Any]       =   '''a castle next to a river'''
								UpperCAmelCase_     :   Any       =   {
								    '''editing_prompt''': ['''boat on a river, boat''', '''monet, impression, sunrise'''],
								    '''reverse_editing_direction''': False,
								    '''edit_warmup_steps''': [15, 18],
								    '''edit_guidance_scale''': 6,
								    '''edit_threshold''': [0.9, 0.8],
								    '''edit_momentum_scale''': 0.5,
								    '''edit_mom_beta''': 0.6,
								}

								UpperCAmelCase_     :   Tuple       =   48
								UpperCAmelCase_     :   Tuple       =   7

								# no sega enabled
								UpperCAmelCase_     :   List[str]       =   torch.Generator(_A     )
								generator.manual_seed(_A     )
								UpperCAmelCase_     :   str       =   pipe(
								    [prompt]							,				generator=_A							,				guidance_scale=_A							,				num_inference_steps=50							,				output_type='''np'''							,				width=5_12							,				height=5_12							,				)

								UpperCAmelCase_     :   Optional[Any]       =   output.images
								UpperCAmelCase_     :   Optional[int]       =   image[0, -3:, -3:, -1]
								UpperCAmelCase_     :   Dict       =   [
								    0.75_163_555,
								    0.76_037_145,
								    0.61_785,
								    0.9_189_673,
								    0.8_627_701,
								    0.85_189_694,
								    0.8_512_813,
								    0.87_012_076,
								    0.8_312_857,
								]

								assert image.shape == (1, 5_12, 5_12, 3)

								assert np.abs(image_slice.flatten() - expected_slice     ).max() < 1e-2

								# with sega enabled
								# generator = torch.manual_seed(seed)
								generator.manual_seed(_A     )
								UpperCAmelCase_     :   List[str]       =   pipe(
								    [prompt]							,				generator=_A							,				guidance_scale=_A							,				num_inference_steps=50							,				output_type='''np'''							,				width=5_12							,				height=5_12							,				**_A							,				)

								UpperCAmelCase_     :   Union[str, Any]       =   output.images
								UpperCAmelCase_     :   Dict       =   image[0, -3:, -3:, -1]
								UpperCAmelCase_     :   Dict       =   [
								    0.73_553_365,
								    0.7_537_271,
								    0.74_341_905,
								    0.66_480_356,
								    0.6_472_925,
								    0.63_039_416,
								    0.64_812_905,
								    0.6_749_717,
								    0.6_517_102,
								]

								assert image.shape == (1, 5_12, 5_12, 3)

								assert np.abs(image_slice.flatten() - expected_slice     ).max() < 1e-2





					def 						A     (       self       :						Union[str, Any]     )  ->    List[str]:
								UpperCAmelCase_     :   Optional[Any]       =   '''cuda'''
								UpperCAmelCase_     :   Dict       =   StableDiffusionPipeline.from_pretrained('''runwayml/stable-diffusion-v1-5'''							,				torch_dtype=torch.floataa     )
								UpperCAmelCase_     :   Union[str, Any]       =   pipe.to(_A     )
								pipe.set_progress_bar_config(disable=_A     )

								UpperCAmelCase_     :   Dict       =   '''a photo of a cat'''
								UpperCAmelCase_     :   List[Any]       =   {
								    '''editing_prompt''': ['''sunglasses'''],
								    '''reverse_editing_direction''': [False],
								    '''edit_warmup_steps''': 10,
								    '''edit_guidance_scale''': 6,
								    '''edit_threshold''': 0.95,
								    '''edit_momentum_scale''': 0.5,
								    '''edit_mom_beta''': 0.6,
								}

								UpperCAmelCase_     :   Optional[int]       =   3
								UpperCAmelCase_     :   int       =   7

								# no sega enabled
								UpperCAmelCase_     :   Dict       =   torch.Generator(_A     )
								generator.manual_seed(_A     )
								UpperCAmelCase_     :   int       =   pipe(
								    [prompt]							,				generator=_A							,				guidance_scale=_A							,				num_inference_steps=50							,				output_type='''np'''							,				width=5_12							,				height=5_12							,				)

								UpperCAmelCase_     :   Optional[int]       =   output.images
								UpperCAmelCase_     :   Any       =   image[0, -3:, -3:, -1]
								UpperCAmelCase_     :   List[Any]       =   [
								    0.34_887_695,
								    0.3_876_953,
								    0.375,
								    0.34_423_828,
								    0.3_581_543,
								    0.35_717_773,
								    0.3_383_789,
								    0.34_570_312,
								    0.359_375,
								]

								assert image.shape == (1, 5_12, 5_12, 3)

								assert np.abs(image_slice.flatten() - expected_slice     ).max() < 1e-2

								# with sega enabled
								# generator = torch.manual_seed(seed)
								generator.manual_seed(_A     )
								UpperCAmelCase_     :   Union[str, Any]       =   pipe(
								    [prompt]							,				generator=_A							,				guidance_scale=_A							,				num_inference_steps=50							,				output_type='''np'''							,				width=5_12							,				height=5_12							,				**_A							,				)

								UpperCAmelCase_     :   Optional[int]       =   output.images
								UpperCAmelCase_     :   Dict       =   image[0, -3:, -3:, -1]
								UpperCAmelCase_     :   Optional[int]       =   [
								    0.42_285_156,
								    0.36_914_062,
								    0.29_077_148,
								    0.42_041_016,
								    0.41_918_945,
								    0.35_498_047,
								    0.3_618_164,
								    0.4_423_828,
								    0.43_115_234,
								]

								assert image.shape == (1, 5_12, 5_12, 3)

								assert np.abs(image_slice.flatten() - expected_slice     ).max() < 1e-2










'''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						)


