
from __future__ import annotations

def 		UpperCamelCase						(   lowercase_			,			lowercase_ )		->						list[int]:


  '''simple docstring'''






  lowercase__	: List[str]     		=   0
  lowercase__	: List[Any]     		=   len(lowercase_ ) - 1

  while i < j:
    if nums[i] + nums[j] == target:
      return [i, j]
    elif nums[i] + nums[j] < target:
      lowercase__	: Optional[Any]     		=   i + 1
    else:
      lowercase__	: int     		=   j - 1

  return []


if __name__ == "__main__":
     import doctest

     doctest.testmod()
     print(f'''{two_pointer([2, 7, 1_1, 1_5], 9) = }''')







'''simple docstring'''


import tempfile
import unittest

from transformers import TaConfig, is_torch_available
from transformers.testing_utils import (
    require_sentencepiece,
    require_tokenizers,
    require_torch,
    slow,
    torch_device,
)

from ...generation.test_utils import GenerationTesterMixin
from ...test_modeling_common import ModelTesterMixin, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
					import torch

					from transformers import AutoTokenizer, UMTaForConditionalGeneration, UMTaForQuestionAnswering, UMTaModel






class     A :





							def __init__(   self					:				List[str]  ,		__a					:				Any  ,		__a					:				int=9_9  ,		__a					:				Any=1_3  ,		__a					:				Tuple=7  ,		__a					:				Tuple=9  ,		__a					:				Tuple=True  ,		__a					:				Union[str, Any]=True  ,		__a					:				List[Any]=False  ,		__a					:				Optional[Any]=3_2  ,		__a					:				str=5  ,		__a					:				Optional[int]=4  ,		__a					:				Union[str, Any]=3_7  ,		__a					:				List[str]=8  ,		__a					:				Optional[int]=0.1  ,		__a					:				List[str]=0.0_0_2  ,		__a					:				List[Any]=1  ,		__a					:				str=0  ,		__a					:				Dict=0  ,		__a					:				int=None  ,		__a					:				List[Any]=None  ,		)				->						Tuple:
								__UpperCAmelCase      					=      parent
								__UpperCAmelCase      					=      batch_size
								__UpperCAmelCase      					=      encoder_seq_length
								__UpperCAmelCase      					=      decoder_seq_length
								# For common tests
								__UpperCAmelCase      					=      self.decoder_seq_length
								__UpperCAmelCase      					=      is_training
								__UpperCAmelCase      					=      use_attention_mask
								__UpperCAmelCase      					=      use_labels
								__UpperCAmelCase      					=      vocab_size
								__UpperCAmelCase      					=      hidden_size
								__UpperCAmelCase      					=      num_hidden_layers
								__UpperCAmelCase      					=      num_attention_heads
								__UpperCAmelCase      					=      d_ff
								__UpperCAmelCase      					=      relative_attention_num_buckets
								__UpperCAmelCase      					=      dropout_rate
								__UpperCAmelCase      					=      initializer_factor
								__UpperCAmelCase      					=      eos_token_id
								__UpperCAmelCase      					=      pad_token_id
								__UpperCAmelCase      					=      decoder_start_token_id
								__UpperCAmelCase      					=      None
								__UpperCAmelCase      					=      decoder_layers





							def    snake_case__    (   self					:				Union[str, Any]						)				->						int:
								return TaConfig.from_pretrained('''google/umt5-base'''						)





							def    snake_case__    (   self					:				List[Any]  ,		__a					:				List[str]  ,		__a					:				str  ,		__a					:				Optional[int]  ,		__a					:				List[Any]=None  ,		__a					:				List[Any]=None  ,		__a					:				Any=None  ,		__a					:				str=None  ,		__a					:				Any=None  ,		)				->						List[Any]:
								if attention_mask is None:
									__UpperCAmelCase      					=      input_ids.ne(config.pad_token_id						)
								if decoder_attention_mask is None:
									__UpperCAmelCase      					=      decoder_input_ids.ne(config.pad_token_id						)
								if head_mask is None:
									__UpperCAmelCase      					=      torch.ones(config.num_hidden_layers  ,		config.num_attention_heads  ,		device=__a						)
								if decoder_head_mask is None:
									__UpperCAmelCase      					=      torch.ones(config.num_decoder_layers  ,		config.num_attention_heads  ,		device=__a						)
								if cross_attn_head_mask is None:
									__UpperCAmelCase      					=      torch.ones(
									    config.num_decoder_layers  ,		config.num_attention_heads  ,		device=__a						)
								return {
								    "input_ids": input_ids,
								    "decoder_input_ids": decoder_input_ids,
								    "attention_mask": attention_mask,
								    "decoder_attention_mask": decoder_attention_mask,
								    "head_mask": head_mask,
								    "decoder_head_mask": decoder_head_mask,
								    "cross_attn_head_mask": cross_attn_head_mask,
								}





							def    snake_case__    (   self					:				List[str]						)				->						Dict:
								__UpperCAmelCase      					=      ids_tensor([self.batch_size, self.encoder_seq_length]  ,		self.vocab_size						)
								__UpperCAmelCase      					=      ids_tensor([self.batch_size, self.decoder_seq_length]  ,		self.vocab_size						)

								# we need to clamp the input ids here to avoid having pad token in between
								# this is because for NllbMoe the position_ids are prepared such that
								# all pad tokens have pos id = 2 and rest are between 2..seq_length
								# and the seq_length here is seq_length - num_pad_tokens
								# but when using past, there is no way of knowing if the past input ids had
								# pad tokens in them, which results in incorrect seq_lenth and which in turn results in
								# position_ids being off by num_pad_tokens in past input
								__UpperCAmelCase      					=      input_ids.clamp(self.pad_token_id + 1						)
								__UpperCAmelCase      					=      decoder_input_ids.clamp(self.pad_token_id + 1						)

								__UpperCAmelCase      					=      self.get_config()
								__UpperCAmelCase      					=      config.num_attention_heads
								__UpperCAmelCase      					=      self.prepare_inputs_dict(__a  ,		__a  ,		__a						)
								return config, input_dict





							def    snake_case__    (   self					:				Union[str, Any]						)				->						Optional[Any]:
								__UpperCAmelCase					,      __UpperCAmelCase      					=      self.prepare_config_and_inputs()
								return config, inputs_dict





							def    snake_case__    (   self					:				int						)				->						Optional[int]:
								return TaConfig(
								    vocab_size=1_6_6  ,		d_model=self.hidden_size  ,		d_ff=self.d_ff  ,		d_kv=self.hidden_size // self.num_attention_heads  ,		num_layers=self.num_hidden_layers  ,		num_decoder_layers=self.decoder_layers  ,		num_heads=self.num_attention_heads  ,		relative_attention_num_buckets=self.relative_attention_num_buckets  ,		dropout_rate=self.dropout_rate  ,		initializer_factor=self.initializer_factor  ,		eos_token_id=self.eos_token_id  ,		bos_token_id=self.pad_token_id  ,		pad_token_id=self.pad_token_id  ,		decoder_start_token_id=self.decoder_start_token_id  ,		)





							def    snake_case__    (   self					:				Optional[int]						)				->						Any:
								return TaConfig(
								    vocab_size=self.vocab_size  ,		d_model=self.hidden_size  ,		d_ff=self.d_ff  ,		d_kv=self.hidden_size // self.num_attention_heads  ,		num_layers=self.num_hidden_layers  ,		num_decoder_layers=self.decoder_layers  ,		num_heads=self.num_attention_heads  ,		relative_attention_num_buckets=self.relative_attention_num_buckets  ,		dropout_rate=self.dropout_rate  ,		initializer_factor=self.initializer_factor  ,		eos_token_id=self.eos_token_id  ,		bos_token_id=self.pad_token_id  ,		pad_token_id=self.pad_token_id  ,		decoder_start_token_id=self.decoder_start_token_id  ,		)





							def    snake_case__    (   self					:				int  ,		__a					:				Any  ,		__a					:				Union[str, Any]  ,		__a					:				List[Any]  ,		__a					:				Dict  ,		__a					:				Optional[Any]  ,		__a					:				int  ,		)				->						List[Any]:
								__UpperCAmelCase      					=      UMTaModel(config=__a						)
								model.to(__a						)
								model.eval()
								__UpperCAmelCase      					=      model(
								    input_ids=__a  ,		decoder_input_ids=__a  ,		attention_mask=__a  ,		decoder_attention_mask=__a  ,		)
								__UpperCAmelCase      					=      model(input_ids=__a  ,		decoder_input_ids=__a						)
								__UpperCAmelCase      					=      result.last_hidden_state
								__UpperCAmelCase      					=      result.past_key_values
								__UpperCAmelCase      					=      result.encoder_last_hidden_state

								self.parent.assertEqual(encoder_output.size()  ,		(self.batch_size, self.encoder_seq_length, self.hidden_size)						)
								self.parent.assertEqual(decoder_output.size()  ,		(self.batch_size, self.decoder_seq_length, self.hidden_size)						)
								# There should be `num_layers` key value embeddings stored in decoder_past
								self.parent.assertEqual(len(__a						)  ,		config.num_layers						)
								# There should be a self attn key, a self attn value, a cross attn key and a cross attn value stored in each decoder_past tuple
								self.parent.assertEqual(len(decoder_past[0]						)  ,		4						)





							def    snake_case__    (   self					:				List[str]  ,		__a					:				Any  ,		__a					:				Tuple  ,		__a					:				List[str]  ,		__a					:				Optional[Any]  ,		__a					:				Dict  ,		__a					:				Any  ,		)				->						Optional[Any]:
								__UpperCAmelCase      					=      UMTaModel(config=__a						).get_decoder().to(__a						).eval()
								# first forward pass
								__UpperCAmelCase      					=      model(__a  ,		use_cache=__a						)
								__UpperCAmelCase      					=      model(__a						)
								__UpperCAmelCase      					=      model(__a  ,		use_cache=__a						)

								self.parent.assertTrue(len(__a						) == len(__a						)						)
								self.parent.assertTrue(len(__a						) == len(__a						) + 1						)

								__UpperCAmelCase					,      __UpperCAmelCase      					=      outputs.to_tuple()

								# create hypothetical next token and extent to next_input_ids
								__UpperCAmelCase      					=      ids_tensor((self.batch_size, 1)  ,		config.vocab_size						)

								# append to next input_ids and
								__UpperCAmelCase      					=      torch.cat([input_ids, next_tokens]  ,		dim=-1						)

								__UpperCAmelCase      					=      model(__a						)['''last_hidden_state''']
								__UpperCAmelCase      					=      model(__a  ,		past_key_values=__a						)['''last_hidden_state''']

								# select random slice
								__UpperCAmelCase      					=      ids_tensor((1,)  ,		output_from_past.shape[-1]						).item()
								__UpperCAmelCase      					=      output_from_no_past[:, -1, random_slice_idx].detach()
								__UpperCAmelCase      					=      output_from_past[:, 0, random_slice_idx].detach()

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






							def    snake_case__    (   self					:				List[Any]  ,		__a					:				Union[str, Any]  ,		__a					:				Dict  ,		)				->						Optional[int]:
								__UpperCAmelCase      					=      UMTaModel(config=__a						).to(__a						).half().eval()
								__UpperCAmelCase      					=      model(**__a						)['''last_hidden_state''']
								self.parent.assertFalse(torch.isnan(__a						).any().item()						)






@require_torch
class     A ( UpperCAmelCase							,						UpperCAmelCase							,						UpperCAmelCase							,						unittest.TestCase ):
							a_										=   (
							    (UMTaModel, UMTaForConditionalGeneration, UMTaForQuestionAnswering) if is_torch_available() else ()
							)
							a_										=   (UMTaForConditionalGeneration,) if is_torch_available() else ()
							a_										=   (
							    {
							        '''conversational''': UMTaForConditionalGeneration,
							        '''feature-extraction''': UMTaModel,
							        '''summarization''': UMTaForConditionalGeneration,
							        '''text2text-generation''': UMTaForConditionalGeneration,
							        '''translation''': UMTaForConditionalGeneration,
							        '''question-answering''': UMTaForQuestionAnswering,
							    }
							    if is_torch_available()
							    else {}
							)
							a_										=   True
							a_										=   False
							a_										=   False
							a_										=   True
							a_										=   True
							# The small UMT5 model needs higher percentages for CPU/MP tests
							a_										=   [0.8, 0.9]





							def    snake_case__    (   self					:				Tuple						)				->						Optional[int]:
								__UpperCAmelCase      					=      UMTaModelTester(self						)





							@unittest.skip('''Test has a segmentation fault on torch 1.8.0'''						)
							def    snake_case__    (   self					:				str						)				->						Optional[int]:
								__UpperCAmelCase      					=      self.model_tester.prepare_config_and_inputs()
								__UpperCAmelCase      					=      UMTaModel(config_and_inputs[0]						).to(__a						)
								with tempfile.TemporaryDirectory() as tmpdirname:
									torch.onnx.export(
									    __a  ,		(config_and_inputs[1], config_and_inputs[3], config_and_inputs[2])  ,		f"""{tmpdirname}/t5_test.onnx"""  ,		export_params=__a  ,		opset_version=9  ,		input_names=['''input_ids''', '''decoder_input_ids''']  ,		)





							@unittest.skipIf(torch_device == '''cpu'''  ,		'''Cant do half precision'''						)
							def    snake_case__    (   self					:				Union[str, Any]						)				->						List[str]:
								__UpperCAmelCase      					=      self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_model_fpaa_forward(*__a						)





							def    snake_case__    (   self					:				List[Any]						)				->						str:
								__UpperCAmelCase      					=      ['''encoder_attentions''', '''decoder_attentions''', '''cross_attentions''']
								__UpperCAmelCase      					=      self.model_tester.prepare_config_and_inputs()
								__UpperCAmelCase      					=      config_and_inputs[0]
								__UpperCAmelCase      					=      UMTaForConditionalGeneration(__a						).eval()
								model.to(__a						)

								__UpperCAmelCase      					=      {
								    '''head_mask''': torch.zeros(config.num_layers  ,		config.num_heads  ,		device=__a						),
								    '''decoder_head_mask''': torch.zeros(config.num_decoder_layers  ,		config.num_heads  ,		device=__a						),
								    '''cross_attn_head_mask''': torch.zeros(config.num_decoder_layers  ,		config.num_heads  ,		device=__a						),
								}

								for attn_name, (name, mask) in zip(__a  ,		head_masking.items()						):
									__UpperCAmelCase      					=      {name: mask}
									# Explicitly pass decoder_head_mask as it is required from T5 model when head_mask specified
									if name == "head_mask":
										__UpperCAmelCase      					=      torch.ones(
										    config.num_decoder_layers  ,		config.num_heads  ,		device=__a						)

									__UpperCAmelCase      					=      model.generate(
									    config_and_inputs[1]['''input_ids''']  ,		num_beams=1  ,		max_length=3  ,		output_attentions=__a  ,		return_dict_in_generate=__a  ,		**__a  ,		)
									# We check the state of decoder_attentions and cross_attentions just from the last step
									__UpperCAmelCase      					=      out[attn_name] if attn_name == attention_names[0] else out[attn_name][-1]
									self.assertEqual(sum([w.sum().item() for w in attn_weights]						)  ,		0.0						)






							@unittest.skip('''Does not work on the tiny model as we keep hitting edge cases.'''						)
							def    snake_case__    (   self					:				Optional[int]						)				->						int:
								pass






@require_torch
@require_sentencepiece
@require_tokenizers
class     A ( unittest.TestCase ):





							@slow
							@unittest.skip(
							    '''Unless we stop stripping left and right by default for all special tokens, the expected ids obtained here will not match the original ones. Wait for https://github.com/huggingface/transformers/pull/23909 to be merged'''						)
							def    snake_case__    (   self					:				Any						)				->						int:
								__UpperCAmelCase      					=      UMTaForConditionalGeneration.from_pretrained('''google/umt5-small'''  ,		return_dict=__a						).to(__a						)
								__UpperCAmelCase      					=      AutoTokenizer.from_pretrained('''google/umt5-small'''  ,		use_fast=__a  ,		legacy=__a						)
								__UpperCAmelCase      					=      [
								    '''Bonjour monsieur <extra_id_0> bien <extra_id_1>.''',
								    '''No se como puedo <extra_id_0>.''',
								    '''This is the reason why we <extra_id_0> them.''',
								    '''The <extra_id_0> walks in <extra_id_1>, seats''',
								    '''A <extra_id_0> walks into a bar and orders a <extra_id_1> with <extra_id_2> pinch of <extra_id_3>.''',
								]
								__UpperCAmelCase      					=      tokenizer(__a  ,		return_tensors='''pt'''  ,		padding=__a						).input_ids
								# fmt: off
								__UpperCAmelCase      					=      torch.tensor(
								    [
								        [ 3_8_5_3_0, 2_1_0_7_0_3, 2_5_6_2_9_9, 1_4_1_0, 2_5_6_2_9_8, 2_7_4, 1, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0],
								        [   8_2_6, 3_2_1, 6_7_1, 2_5_9_2_2, 2_5_6_2_9_9, 2_7_4, 1, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0],
								        [  1_4_6_0, 3_3_9, 3_1_2, 1_9_0_1_4, 1_0_6_2_0, 7_5_8, 2_5_6_2_9_9, 2_3_5_5,2_7_4, 1, 0, 0, 0, 0, 0, 0,0, 0],
								        [   5_1_7, 2_5_6_2_9_9, 1_4_8_6_9, 2_8_1, 3_0_1, 2_5_6_2_9_8, 2_7_5, 1_1_9_9_8_3,1, 0, 0, 0, 0, 0, 0, 0,0, 0],
								        [   3_2_0, 2_5_6_2_9_9, 1_4_8_6_9, 2_8_1, 2_2_3_4, 2_8_9, 2_2_7_5, 3_3_3,6_1_3_9_1, 2_8_9, 2_5_6_2_9_8, 5_4_3, 2_5_6_2_9_7, 1_6_8_7_1_4, 3_2_9, 2_5_6_2_9_6,2_7_4, 1],
								    ]						)
								# fmt: on
								torch.testing.assert_allclose(__a  ,		__a						)

								__UpperCAmelCase      					=      model.generate(input_ids.to(__a						)						)
								__UpperCAmelCase      					=      [
								    '''<pad><extra_id_0> et<extra_id_1> [eod] <extra_id_2><extra_id_55>.. [eod] 💐 💐 💐 💐 💐 💐 💐 💐 💐 💐 💐 <extra_id_56>ajšietosto<extra_id_56>lleux<extra_id_19><extra_id_6>ajšie</s>''',
								    '''<pad><extra_id_0>.<extra_id_1>.,<0x0A>...spech <0x0A><extra_id_20> <extra_id_21></s><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad>''',
								    '''<pad><extra_id_0> are not going to be a part of the world. We are not going to be a part of<extra_id_1> and<extra_id_2><0x0A><extra_id_48>.<extra_id_48></s><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad>''',
								    '''<pad><extra_id_0> door<extra_id_1>, the door<extra_id_2> 피해[/</s><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad>''',
								    '''<pad><extra_id_0>nyone who<extra_id_1> drink<extra_id_2> a<extra_id_3> alcohol<extra_id_4> A<extra_id_5> A. This<extra_id_6> I<extra_id_7><extra_id_52><extra_id_53></s><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad><pad>''',
								]
								__UpperCAmelCase      					=      tokenizer.batch_decode(__a						)
								self.assertEqual(__a  ,		__a						)
