


'''simple docstring'''




import unittest

from transformers import is_torch_available
from transformers.testing_utils import require_torch, slow, torch_device

from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, floats_tensor, ids_tensor, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
				import torch

				from transformers import (
				    RemBertConfig,
				    RemBertForCausalLM,
				    RemBertForMaskedLM,
				    RemBertForMultipleChoice,
				    RemBertForQuestionAnswering,
				    RemBertForSequenceClassification,
				    RemBertForTokenClassification,
				    RemBertModel,
				)
				from transformers.models.rembert.modeling_rembert import REMBERT_PRETRAINED_MODEL_ARCHIVE_LIST





class _snake_case   :
							"""simple docstring"""





							def __init__(   self			,				__A			,				__A=13			,				__A=7			,				__A=True			,				__A=True			,				__A=True			,				__A=True			,				__A=99			,				__A=32			,				__A=18			,				__A=43			,				__A=5			,				__A=4			,				__A=37			,				__A="gelu"			,				__A=0.1			,				__A=0.1			,				__A=512			,				__A=16			,				__A=2			,				__A=0.02			,				__A=3			,				__A=4			,				__A=None			,				)     ->str:



											"""simple docstring"""







											__lowerCamelCase		:      Tuple											=					parent
											__lowerCamelCase		:      List[Any]											=					batch_size
											__lowerCamelCase		:      List[str]											=					seq_length
											__lowerCamelCase		:      List[Any]											=					is_training
											__lowerCamelCase		:      Optional[Any]											=					use_input_mask
											__lowerCamelCase		:      str											=					use_token_type_ids
											__lowerCamelCase		:      Any											=					use_labels
											__lowerCamelCase		:      Union[str, Any]											=					vocab_size
											__lowerCamelCase		:      Optional[int]											=					hidden_size
											__lowerCamelCase		:      int											=					input_embedding_size
											__lowerCamelCase		:      List[Any]											=					output_embedding_size
											__lowerCamelCase		:      str											=					num_hidden_layers
											__lowerCamelCase		:      int											=					num_attention_heads
											__lowerCamelCase		:      Dict											=					intermediate_size
											__lowerCamelCase		:      str											=					hidden_act
											__lowerCamelCase		:      str											=					hidden_dropout_prob
											__lowerCamelCase		:      Optional[Any]											=					attention_probs_dropout_prob
											__lowerCamelCase		:      Any											=					max_position_embeddings
											__lowerCamelCase		:      Dict											=					type_vocab_size
											__lowerCamelCase		:      str											=					type_sequence_label_size
											__lowerCamelCase		:      Dict											=					initializer_range
											__lowerCamelCase		:      int											=					num_labels
											__lowerCamelCase		:      int											=					num_choices
											__lowerCamelCase		:      Dict											=					scope







							def 		__SCREAMING_SNAKE_CASE(   self	)     ->List[Any]:



											"""simple docstring"""







											__lowerCamelCase		:      List[Any]											=					ids_tensor([self.batch_size, self.seq_length]			,				self.vocab_size	)

											__lowerCamelCase		:      List[Any]											=					None
											if self.use_input_mask:
															__lowerCamelCase		:      Optional[Any]											=					random_attention_mask([self.batch_size, self.seq_length]	)

											__lowerCamelCase		:      List[Any]											=					None
											if self.use_token_type_ids:
															__lowerCamelCase		:      List[Any]											=					ids_tensor([self.batch_size, self.seq_length]			,				self.type_vocab_size	)

											__lowerCamelCase		:      Optional[Any]											=					None
											__lowerCamelCase		:      Optional[int]											=					None
											__lowerCamelCase		:      Dict											=					None
											if self.use_labels:
															__lowerCamelCase		:      str											=					ids_tensor([self.batch_size]			,				self.type_sequence_label_size	)
															__lowerCamelCase		:      Optional[int]											=					ids_tensor([self.batch_size, self.seq_length]			,				self.num_labels	)
															__lowerCamelCase		:      Dict											=					ids_tensor([self.batch_size]			,				self.num_choices	)

											__lowerCamelCase		:      List[str]											=					RemBertConfig(
											    vocab_size=self.vocab_size			,				hidden_size=self.hidden_size			,				input_embedding_size=self.input_embedding_size			,				output_embedding_size=self.output_embedding_size			,				num_hidden_layers=self.num_hidden_layers			,				num_attention_heads=self.num_attention_heads			,				intermediate_size=self.intermediate_size			,				hidden_act=self.hidden_act			,				hidden_dropout_prob=self.hidden_dropout_prob			,				attention_probs_dropout_prob=self.attention_probs_dropout_prob			,				max_position_embeddings=self.max_position_embeddings			,				type_vocab_size=self.type_vocab_size			,				is_decoder=__A			,				initializer_range=self.initializer_range			,				)

											return config, input_ids, token_type_ids, input_mask, sequence_labels, token_labels, choice_labels







							def 		__SCREAMING_SNAKE_CASE(   self	)     ->Tuple:



											"""simple docstring"""







											(
											    (
											    __lowerCamelCase
											)						,					(
											    __lowerCamelCase
											)						,					(
											    __lowerCamelCase
											)						,					(
											    __lowerCamelCase
											)						,					(
											    __lowerCamelCase
											)						,					(
											    __lowerCamelCase
											)						,					(
											    __lowerCamelCase
											)						,					
											)		:      Optional[Any]											=					self.prepare_config_and_inputs()

											__lowerCamelCase		:      Optional[Any]											=					True
											__lowerCamelCase		:      Dict											=					floats_tensor([self.batch_size, self.seq_length, self.hidden_size]	)
											__lowerCamelCase		:      Optional[int]											=					ids_tensor([self.batch_size, self.seq_length]			,				vocab_size=2	)

											return (
											    config,
											    input_ids,
											    token_type_ids,
											    input_mask,
											    sequence_labels,
											    token_labels,
											    choice_labels,
											    encoder_hidden_states,
											    encoder_attention_mask,
											)







							def 		__SCREAMING_SNAKE_CASE(   self			,				__A			,				__A			,				__A			,				__A			,				__A			,				__A			,				__A	)     ->Dict:



											"""simple docstring"""







											__lowerCamelCase		:      List[str]											=					RemBertModel(config=__A	)
											model.to(__A	)
											model.eval()
											__lowerCamelCase		:      Tuple											=					model(__A			,				attention_mask=__A			,				token_type_ids=__A	)
											__lowerCamelCase		:      Dict											=					model(__A			,				token_type_ids=__A	)
											__lowerCamelCase		:      int											=					model(__A	)
											self.parent.assertEqual(result.last_hidden_state.shape			,				(self.batch_size, self.seq_length, self.hidden_size)	)







							def 		__SCREAMING_SNAKE_CASE(   self			,				__A			,				__A			,				__A			,				__A			,				__A			,				__A			,				__A			,				__A			,				__A			,				)     ->int:



											"""simple docstring"""







											__lowerCamelCase		:      Union[str, Any]											=					True
											__lowerCamelCase		:      Union[str, Any]											=					RemBertModel(__A	)
											model.to(__A	)
											model.eval()
											__lowerCamelCase		:      List[str]											=					model(
											    __A			,				attention_mask=__A			,				token_type_ids=__A			,				encoder_hidden_states=__A			,				encoder_attention_mask=__A			,				)
											__lowerCamelCase		:      str											=					model(
											    __A			,				attention_mask=__A			,				token_type_ids=__A			,				encoder_hidden_states=__A			,				)
											__lowerCamelCase		:      List[Any]											=					model(__A			,				attention_mask=__A			,				token_type_ids=__A	)
											self.parent.assertEqual(result.last_hidden_state.shape			,				(self.batch_size, self.seq_length, self.hidden_size)	)







							def 		__SCREAMING_SNAKE_CASE(   self			,				__A			,				__A			,				__A			,				__A			,				__A			,				__A			,				__A			,				__A			,				__A			,				)     ->Tuple:



											"""simple docstring"""







											__lowerCamelCase		:      Dict											=					RemBertForCausalLM(config=__A	)
											model.to(__A	)
											model.eval()
											__lowerCamelCase		:      int											=					model(__A			,				attention_mask=__A			,				token_type_ids=__A			,				labels=__A	)
											self.parent.assertEqual(result.logits.shape			,				(self.batch_size, self.seq_length, self.vocab_size)	)







							def 		__SCREAMING_SNAKE_CASE(   self			,				__A			,				__A			,				__A			,				__A			,				__A			,				__A			,				__A	)     ->Any:



											"""simple docstring"""







											__lowerCamelCase		:      int											=					RemBertForMaskedLM(config=__A	)
											model.to(__A	)
											model.eval()
											__lowerCamelCase		:      Optional[int]											=					model(__A			,				attention_mask=__A			,				token_type_ids=__A			,				labels=__A	)
											self.parent.assertEqual(result.logits.shape			,				(self.batch_size, self.seq_length, self.vocab_size)	)







							def 		__SCREAMING_SNAKE_CASE(   self			,				__A			,				__A			,				__A			,				__A			,				__A			,				__A			,				__A			,				__A			,				__A			,				)     ->str:



											"""simple docstring"""







											__lowerCamelCase		:      Optional[Any]											=					True
											__lowerCamelCase		:      Tuple											=					True
											__lowerCamelCase		:      str											=					RemBertForCausalLM(config=__A	)
											model.to(__A	)
											model.eval()

											# first forward pass
											__lowerCamelCase		:      Optional[Any]											=					model(
											    __A			,				attention_mask=__A			,				encoder_hidden_states=__A			,				encoder_attention_mask=__A			,				use_cache=__A			,				)
											__lowerCamelCase		:      List[str]											=					outputs.past_key_values

											# create hypothetical multiple next token and extent to next_input_ids
											__lowerCamelCase		:      Tuple											=					ids_tensor((self.batch_size, 3)			,				config.vocab_size	)
											__lowerCamelCase		:      Any											=					ids_tensor((self.batch_size, 3)			,				vocab_size=2	)

											# append to next input_ids and
											__lowerCamelCase		:      Tuple											=					torch.cat([input_ids, next_tokens]			,				dim=-1	)
											__lowerCamelCase		:      Any											=					torch.cat([input_mask, next_mask]			,				dim=-1	)

											__lowerCamelCase		:      Dict											=					model(
											    __A			,				attention_mask=__A			,				encoder_hidden_states=__A			,				encoder_attention_mask=__A			,				output_hidden_states=__A			,				)["hidden_states"][0]
											__lowerCamelCase		:      Dict											=					model(
											    __A			,				attention_mask=__A			,				encoder_hidden_states=__A			,				encoder_attention_mask=__A			,				past_key_values=__A			,				output_hidden_states=__A			,				)["hidden_states"][0]

											# select random slice
											__lowerCamelCase		:      int											=					ids_tensor((1,)			,				output_from_past.shape[-1]	).item()
											__lowerCamelCase		:      str											=					output_from_no_past[:, -3:, random_slice_idx].detach()
											__lowerCamelCase		:      Tuple											=					output_from_past[:, :, random_slice_idx].detach()

											self.parent.assertTrue(output_from_past_slice.shape[1] == next_tokens.shape[1]	)

											# test that outputs are equal for slice
											self.parent.assertTrue(torch.allclose(__A			,				__A			,				atol=1E-3	)	)







							def 		__SCREAMING_SNAKE_CASE(   self			,				__A			,				__A			,				__A			,				__A			,				__A			,				__A			,				__A	)     ->List[str]:



											"""simple docstring"""







											__lowerCamelCase		:      int											=					RemBertForQuestionAnswering(config=__A	)
											model.to(__A	)
											model.eval()
											__lowerCamelCase		:      Optional[Any]											=					model(
											    __A			,				attention_mask=__A			,				token_type_ids=__A			,				start_positions=__A			,				end_positions=__A			,				)
											self.parent.assertEqual(result.start_logits.shape			,				(self.batch_size, self.seq_length)	)
											self.parent.assertEqual(result.end_logits.shape			,				(self.batch_size, self.seq_length)	)







							def 		__SCREAMING_SNAKE_CASE(   self			,				__A			,				__A			,				__A			,				__A			,				__A			,				__A			,				__A	)     ->Optional[int]:



											"""simple docstring"""







											__lowerCamelCase		:      int											=					self.num_labels
											__lowerCamelCase		:      Dict											=					RemBertForSequenceClassification(__A	)
											model.to(__A	)
											model.eval()
											__lowerCamelCase		:      List[str]											=					model(__A			,				attention_mask=__A			,				token_type_ids=__A			,				labels=__A	)
											self.parent.assertEqual(result.logits.shape			,				(self.batch_size, self.num_labels)	)







							def 		__SCREAMING_SNAKE_CASE(   self			,				__A			,				__A			,				__A			,				__A			,				__A			,				__A			,				__A	)     ->List[Any]:



											"""simple docstring"""







											__lowerCamelCase		:      Optional[int]											=					self.num_labels
											__lowerCamelCase		:      Optional[int]											=					RemBertForTokenClassification(config=__A	)
											model.to(__A	)
											model.eval()
											__lowerCamelCase		:      List[str]											=					model(__A			,				attention_mask=__A			,				token_type_ids=__A			,				labels=__A	)
											self.parent.assertEqual(result.logits.shape			,				(self.batch_size, self.seq_length, self.num_labels)	)







							def 		__SCREAMING_SNAKE_CASE(   self			,				__A			,				__A			,				__A			,				__A			,				__A			,				__A			,				__A	)     ->Tuple:



											"""simple docstring"""







											__lowerCamelCase		:      Optional[Any]											=					self.num_choices
											__lowerCamelCase		:      Optional[int]											=					RemBertForMultipleChoice(config=__A	)
											model.to(__A	)
											model.eval()
											__lowerCamelCase		:      Optional[Any]											=					input_ids.unsqueeze(1	).expand(-1			,				self.num_choices			,				-1	).contiguous()
											__lowerCamelCase		:      str											=					token_type_ids.unsqueeze(1	).expand(-1			,				self.num_choices			,				-1	).contiguous()
											__lowerCamelCase		:      Optional[Any]											=					input_mask.unsqueeze(1	).expand(-1			,				self.num_choices			,				-1	).contiguous()
											__lowerCamelCase		:      int											=					model(
											    __A			,				attention_mask=__A			,				token_type_ids=__A			,				labels=__A			,				)
											self.parent.assertEqual(result.logits.shape			,				(self.batch_size, self.num_choices)	)







							def 		__SCREAMING_SNAKE_CASE(   self	)     ->Optional[int]:



											"""simple docstring"""







											__lowerCamelCase		:      List[Any]											=					self.prepare_config_and_inputs()
											(
											    (
											    __lowerCamelCase
											)						,					(
											    __lowerCamelCase
											)						,					(
											    __lowerCamelCase
											)						,					(
											    __lowerCamelCase
											)						,					(
											    __lowerCamelCase
											)						,					(
											    __lowerCamelCase
											)						,					(
											    __lowerCamelCase
											)						,					
											)		:      Optional[int]											=					config_and_inputs
											__lowerCamelCase		:      str											=					{"input_ids": input_ids, "token_type_ids": token_type_ids, "attention_mask": input_mask}
											return config, inputs_dict





@require_torch
class _snake_case   ( a__    ,   a__    ,   unittest.TestCase   ):
							"""simple docstring"""





							__a												=     (
							    (
							        RemBertModel,
							        RemBertForMaskedLM,
							        RemBertForCausalLM,
							        RemBertForMultipleChoice,
							        RemBertForQuestionAnswering,
							        RemBertForSequenceClassification,
							        RemBertForTokenClassification,
							    )
							    if is_torch_available()
							    else ()
							)
							__a												=     (RemBertForCausalLM,) if is_torch_available() else ()
							__a												=     (
							    {
							        '''feature-extraction''': RemBertModel,
							        '''fill-mask''': RemBertForMaskedLM,
							        '''question-answering''': RemBertForQuestionAnswering,
							        '''text-classification''': RemBertForSequenceClassification,
							        '''text-generation''': RemBertForCausalLM,
							        '''token-classification''': RemBertForTokenClassification,
							        '''zero-shot''': RemBertForSequenceClassification,
							    }
							    if is_torch_available()
							    else {}
							)







							def 		__SCREAMING_SNAKE_CASE(   self	)     ->Tuple:



											"""simple docstring"""







											__lowerCamelCase		:      Tuple											=					RemBertModelTester(self	)
											__lowerCamelCase		:      Optional[Any]											=					ConfigTester(self			,				config_class=__A			,				hidden_size=37	)







							def 		__SCREAMING_SNAKE_CASE(   self	)     ->Dict:



											"""simple docstring"""







											self.config_tester.run_common_tests()







							def 		__SCREAMING_SNAKE_CASE(   self	)     ->Union[str, Any]:



											"""simple docstring"""







											__lowerCamelCase		:      List[Any]											=					self.model_tester.prepare_config_and_inputs()
											self.model_tester.create_and_check_model(*__A	)







							def 		__SCREAMING_SNAKE_CASE(   self	)     ->Any:



											"""simple docstring"""







											__lowerCamelCase		:      Tuple											=					self.model_tester.prepare_config_and_inputs()
											for type in ["absolute", "relative_key", "relative_key_query"]:
															__lowerCamelCase		:      int											=					type
															self.model_tester.create_and_check_model(*__A	)







							def 		__SCREAMING_SNAKE_CASE(   self	)     ->Dict:



											"""simple docstring"""







											__lowerCamelCase		:      Optional[int]											=					self.model_tester.prepare_config_and_inputs()
											self.model_tester.create_and_check_for_masked_lm(*__A	)







							def 		__SCREAMING_SNAKE_CASE(   self	)     ->Optional[Any]:



											"""simple docstring"""







											__lowerCamelCase		:      Tuple											=					self.model_tester.prepare_config_and_inputs()
											self.model_tester.create_and_check_for_multiple_choice(*__A	)







							def 		__SCREAMING_SNAKE_CASE(   self	)     ->List[str]:



											"""simple docstring"""







											__lowerCamelCase		:      Tuple											=					self.model_tester.prepare_config_and_inputs_for_decoder()
											self.model_tester.create_and_check_decoder_model_past_large_inputs(*__A	)







							def 		__SCREAMING_SNAKE_CASE(   self	)     ->Any:



											"""simple docstring"""







											__lowerCamelCase		:      Optional[int]											=					self.model_tester.prepare_config_and_inputs()
											self.model_tester.create_and_check_for_question_answering(*__A	)







							def 		__SCREAMING_SNAKE_CASE(   self	)     ->Any:



											"""simple docstring"""







											__lowerCamelCase		:      Dict											=					self.model_tester.prepare_config_and_inputs()
											self.model_tester.create_and_check_for_sequence_classification(*__A	)







							def 		__SCREAMING_SNAKE_CASE(   self	)     ->Any:



											"""simple docstring"""







											__lowerCamelCase		:      Tuple											=					self.model_tester.prepare_config_and_inputs()
											self.model_tester.create_and_check_for_token_classification(*__A	)







							def 		__SCREAMING_SNAKE_CASE(   self	)     ->List[str]:



											"""simple docstring"""







											__lowerCamelCase		:      Any											=					self.model_tester.prepare_config_and_inputs_for_decoder()
											self.model_tester.create_and_check_model_as_decoder(*__A	)







							def 		__SCREAMING_SNAKE_CASE(   self	)     ->int:



											"""simple docstring"""







											(
											    (
											    __lowerCamelCase
											)						,					(
											    __lowerCamelCase
											)						,					(
											    __lowerCamelCase
											)						,					(
											    __lowerCamelCase
											)						,					(
											    __lowerCamelCase
											)						,					(
											    __lowerCamelCase
											)						,					(
											    __lowerCamelCase
											)						,					(
											    __lowerCamelCase
											)						,					(
											    __lowerCamelCase
											)						,					
											)		:      Any											=					self.model_tester.prepare_config_and_inputs_for_decoder()

											__lowerCamelCase		:      Union[str, Any]											=					None

											self.model_tester.create_and_check_model_as_decoder(
											    __A			,				__A			,				__A			,				__A			,				__A			,				__A			,				__A			,				__A			,				__A			,				)







							@slow
							def 		__SCREAMING_SNAKE_CASE(   self	)     ->Union[str, Any]:



											"""simple docstring"""







											for model_name in REMBERT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
															__lowerCamelCase		:      Any											=					RemBertModel.from_pretrained(__A	)
															self.assertIsNotNone(__A	)





@require_torch
class _snake_case   ( unittest.TestCase   ):
							"""simple docstring"""





							@slow
							def 		__SCREAMING_SNAKE_CASE(   self	)     ->List[str]:



											"""simple docstring"""







											__lowerCamelCase		:      List[Any]											=					RemBertModel.from_pretrained("google/rembert"	)
											__lowerCamelCase		:      Tuple											=					torch.tensor([[312, 56498, 313, 2125, 313]]	)
											__lowerCamelCase		:      str											=					torch.tensor([[0, 0, 0, 1, 1]]	)
											with torch.no_grad():
															__lowerCamelCase		:      Optional[Any]											=					model(__A			,				token_type_ids=__A			,				output_hidden_states=__A	)

											__lowerCamelCase		:      int											=					1152

											__lowerCamelCase		:      Any											=					torch.Size((1, 5, hidden_size)	)
											self.assertEqual(output["last_hidden_state"].shape			,				__A	)

											__lowerCamelCase		:      Optional[Any]											=					torch.tensor(
											    [
											        [
											            [0.0754, -0.2022, 0.1904],
											            [-0.3354, -0.3692, -0.4791],
											            [-0.2314, -0.6729, -0.0749],
											            [-0.0396, -0.3105, -0.4234],
											            [-0.1571, -0.0525, 0.5353],
											        ]
											    ]	)

											# Running on the original tf implementation gives slightly different results here.
											# Not clear why this variations is present
											# TODO: Find reason for discrepancy
											# expected_original_implementation = [[
											#     [0.07630594074726105, -0.20146065950393677, 0.19107051193714142],
											#     [-0.3405614495277405, -0.36971670389175415, -0.4808273911476135],
											#     [-0.22587086260318756, -0.6656315922737122, -0.07844287157058716],
											#     [-0.04145475849509239, -0.3077218234539032, -0.42316967248916626],
											#     [-0.15887849032878876, -0.054529931396245956, 0.5356100797653198]
											# ]]

											self.assertTrue(torch.allclose(output["last_hidden_state"][:, :, :3]			,				__A			,				atol=1E-4	)	)









'''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   ( a__   ):
							"""simple docstring"""





							__a												=     1
							__a												=     2
							__a												=     3







							def __repr__(   self	)     ->Tuple:



											"""simple docstring"""







											return f'{self.__class__.__name__}.{self.name}'





def 							a_       (						lowercase							,						lowercase							,						lowercase    )			->float:






				'''simple docstring'''

				__lowerCamelCase						,					__lowerCamelCase		:      str											=					point
				return degrees(atana(y - miny							,						x - minx    )    )





def 							a_       (						lowercase							,						lowercase							,						lowercase    )			->Direction:






				'''simple docstring'''

				__lowerCamelCase						,					__lowerCamelCase		:      List[str]											=					starting
				__lowerCamelCase						,					__lowerCamelCase		:      Any											=					via
				__lowerCamelCase						,					__lowerCamelCase		:      str											=					target
				__lowerCamelCase		:      str											=					degrees(atana(ya - ya							,						xa - xa    )    )
				via_angle %= 360
				__lowerCamelCase		:      List[Any]											=					degrees(atana(ya - ya							,						xa - xa    )    )
				target_angle %= 360
				# 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 							a_       (						lowercase    )			->list[tuple[int, int]]:






				'''simple docstring'''

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

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

				__lowerCamelCase		:      Optional[Any]											=					sorted(lowercase							,						key=lambda lowercase    : angle_comparer(lowercase							,						lowercase							,						lowercase    )    )
				# 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)    )

				__lowerCamelCase		:      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.
				__lowerCamelCase		:      str											=					Direction.left

				for i in range(3							,						len(lowercase    )    ):
								while True:
												__lowerCamelCase		:      List[Any]											=					stack[-2]
												__lowerCamelCase		:      str											=					stack[-1]
												__lowerCamelCase		:      int											=					sorted_points[i]
												__lowerCamelCase		:      List[Any]											=					check_direction(lowercase							,						lowercase							,						lowercase    )

												if next_direction == Direction.left:
																__lowerCamelCase		:      Optional[int]											=					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(lowercase    )





