
'''simple docstring'''


from __future__ import annotations
def 					__magic_name__(       UpperCAmelCase__ :       list[list[int]]							,				UpperCAmelCase__ :       int							,				UpperCAmelCase__ :       int							,				UpperCAmelCase__ :       int | float	):
						UpperCamelCase_     ,UpperCamelCase_     :	Union[str, Any]					     =     m - 1, 0
						while i >= 0 and j < n:
												if key == mat[i][j]:
																		print(f"""Key {key} found at row- {i + 1} column- {j + 1}"""	)
																		return
												if key < mat[i][j]:
																		i -= 1
												else:
																		j += 1
						print(f"""Key {key} not found"""	)
def 					__magic_name__(       ):
						UpperCamelCase_     :	List[Any]					     =     [[2, 5, 7], [4, 8, 13], [9, 11, 15], [12, 17, 20]]
						UpperCamelCase_     :	Optional[Any]					     =     int(input("""Enter the element to be searched:"""	)	)
						print(UpperCAmelCase__	)
						search_in_a_sorted_matrix(UpperCAmelCase__							,				len(UpperCAmelCase__	)							,				len(mat[0]	)							,				UpperCAmelCase__	)


if __name__ == "__main__":
	import doctest

	doctest.testmod()
	main()






'''simple docstring'''


import os
import unittest

from transformers import RealmTokenizerFast
from transformers.models.bert.tokenization_bert import (
    VOCAB_FILES_NAMES,
    BasicTokenizer,
    WordpieceTokenizer,
    _is_control,
    _is_punctuation,
    _is_whitespace,
)
from transformers.models.realm.tokenization_realm import RealmTokenizer
from transformers.testing_utils import require_tokenizers, slow

from ...test_tokenization_common import TokenizerTesterMixin, filter_non_english




@require_tokenizers
class     __snake_case			(    _a					,			unittest.TestCase	):
		a_          =					RealmTokenizer
		a_          =					RealmTokenizerFast
		a_          =					True
		a_          =					True
		a_          =					filter_non_english




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






								'''simple docstring'''






								super().setUp()

								UpperCamelCase_     :	Optional[int]					     =     [
								    """[UNK]""",
								    """[CLS]""",
								    """[SEP]""",
								    """[PAD]""",
								    """[MASK]""",
								    """want""",
								    """##want""",
								    """##ed""",
								    """wa""",
								    """un""",
								    """runn""",
								    """##ing""",
								    """,""",
								    """low""",
								    """lowest""",
								]
								UpperCamelCase_     :	Tuple					     =     os.path.join(self.tmpdirname			,    VOCAB_FILES_NAMES["""vocab_file"""])
								with open(self.vocab_file			,    """w"""			,    encoding="""utf-8""") as vocab_writer:
														vocab_writer.write("""""".join([x + """\n""" for x in vocab_tokens]))




		def 	_snake_case	(  self					:Any			,    _SCREAMING_SNAKE_CASE					:List[Any])					->			str:






								'''simple docstring'''






								UpperCamelCase_     :	List[str]					     =     """UNwant\u00E9d,running"""
								UpperCamelCase_     :	Union[str, Any]					     =     """unwanted, running"""
								return input_text, output_text




		def 	_snake_case	(  self					:Any)					->			Any:






								'''simple docstring'''






								UpperCamelCase_     :	str					     =     self.tokenizer_class(self.vocab_file)

								UpperCamelCase_     :	str					     =     tokenizer.tokenize("""UNwant\u00E9d,running""")
								self.assertListEqual(_SCREAMING_SNAKE_CASE			,    ["""un""", """##want""", """##ed""", """,""", """runn""", """##ing"""])
								self.assertListEqual(tokenizer.convert_tokens_to_ids(_SCREAMING_SNAKE_CASE)			,    [9, 6, 7, 1_2, 1_0, 1_1])




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






								'''simple docstring'''






								if not self.test_rust_tokenizer:
														return

								UpperCamelCase_     :	Optional[int]					     =     self.get_tokenizer()
								UpperCamelCase_     :	Union[str, Any]					     =     self.get_rust_tokenizer()

								UpperCamelCase_     :	List[Any]					     =     """UNwant\u00E9d,running"""

								UpperCamelCase_     :	Union[str, Any]					     =     tokenizer.tokenize(_SCREAMING_SNAKE_CASE)
								UpperCamelCase_     :	List[Any]					     =     rust_tokenizer.tokenize(_SCREAMING_SNAKE_CASE)
								self.assertListEqual(_SCREAMING_SNAKE_CASE			,    _SCREAMING_SNAKE_CASE)

								UpperCamelCase_     :	List[Any]					     =     tokenizer.encode(_SCREAMING_SNAKE_CASE			,    add_special_tokens=_SCREAMING_SNAKE_CASE)
								UpperCamelCase_     :	Tuple					     =     rust_tokenizer.encode(_SCREAMING_SNAKE_CASE			,    add_special_tokens=_SCREAMING_SNAKE_CASE)
								self.assertListEqual(_SCREAMING_SNAKE_CASE			,    _SCREAMING_SNAKE_CASE)

								UpperCamelCase_     :	Dict					     =     self.get_rust_tokenizer()
								UpperCamelCase_     :	Optional[int]					     =     tokenizer.encode(_SCREAMING_SNAKE_CASE)
								UpperCamelCase_     :	List[Any]					     =     rust_tokenizer.encode(_SCREAMING_SNAKE_CASE)
								self.assertListEqual(_SCREAMING_SNAKE_CASE			,    _SCREAMING_SNAKE_CASE)

								# With lower casing
								UpperCamelCase_     :	Union[str, Any]					     =     self.get_tokenizer(do_lower_case=_SCREAMING_SNAKE_CASE)
								UpperCamelCase_     :	List[Any]					     =     self.get_rust_tokenizer(do_lower_case=_SCREAMING_SNAKE_CASE)

								UpperCamelCase_     :	List[str]					     =     """UNwant\u00E9d,running"""

								UpperCamelCase_     :	Union[str, Any]					     =     tokenizer.tokenize(_SCREAMING_SNAKE_CASE)
								UpperCamelCase_     :	List[str]					     =     rust_tokenizer.tokenize(_SCREAMING_SNAKE_CASE)
								self.assertListEqual(_SCREAMING_SNAKE_CASE			,    _SCREAMING_SNAKE_CASE)

								UpperCamelCase_     :	Union[str, Any]					     =     tokenizer.encode(_SCREAMING_SNAKE_CASE			,    add_special_tokens=_SCREAMING_SNAKE_CASE)
								UpperCamelCase_     :	str					     =     rust_tokenizer.encode(_SCREAMING_SNAKE_CASE			,    add_special_tokens=_SCREAMING_SNAKE_CASE)
								self.assertListEqual(_SCREAMING_SNAKE_CASE			,    _SCREAMING_SNAKE_CASE)

								UpperCamelCase_     :	Dict					     =     self.get_rust_tokenizer()
								UpperCamelCase_     :	Tuple					     =     tokenizer.encode(_SCREAMING_SNAKE_CASE)
								UpperCamelCase_     :	Dict					     =     rust_tokenizer.encode(_SCREAMING_SNAKE_CASE)
								self.assertListEqual(_SCREAMING_SNAKE_CASE			,    _SCREAMING_SNAKE_CASE)




		def 	_snake_case	(  self					:Tuple)					->			Optional[Any]:






								'''simple docstring'''






								UpperCamelCase_     :	Dict					     =     BasicTokenizer()

								self.assertListEqual(tokenizer.tokenize("""ah\u535A\u63A8zz""")			,    ["""ah""", """\u535A""", """\u63A8""", """zz"""])




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






								'''simple docstring'''






								UpperCamelCase_     :	List[str]					     =     BasicTokenizer(do_lower_case=_SCREAMING_SNAKE_CASE)

								self.assertListEqual(
								    tokenizer.tokenize(""" \tHeLLo!how  \n Are yoU?  """)			,    ["""hello""", """!""", """how""", """are""", """you""", """?"""])
								self.assertListEqual(tokenizer.tokenize("""H\u00E9llo""")			,    ["""hello"""])




		def 	_snake_case	(  self					:Dict)					->			List[str]:






								'''simple docstring'''






								UpperCamelCase_     :	List[Any]					     =     BasicTokenizer(do_lower_case=_SCREAMING_SNAKE_CASE			,    strip_accents=_SCREAMING_SNAKE_CASE)

								self.assertListEqual(
								    tokenizer.tokenize(""" \tHäLLo!how  \n Are yoU?  """)			,    ["""hällo""", """!""", """how""", """are""", """you""", """?"""])
								self.assertListEqual(tokenizer.tokenize("""H\u00E9llo""")			,    ["""h\u00E9llo"""])




		def 	_snake_case	(  self					:int)					->			Dict:






								'''simple docstring'''






								UpperCamelCase_     :	Tuple					     =     BasicTokenizer(do_lower_case=_SCREAMING_SNAKE_CASE			,    strip_accents=_SCREAMING_SNAKE_CASE)

								self.assertListEqual(
								    tokenizer.tokenize(""" \tHäLLo!how  \n Are yoU?  """)			,    ["""hallo""", """!""", """how""", """are""", """you""", """?"""])
								self.assertListEqual(tokenizer.tokenize("""H\u00E9llo""")			,    ["""hello"""])




		def 	_snake_case	(  self					:Optional[int])					->			Any:






								'''simple docstring'''






								UpperCamelCase_     :	Union[str, Any]					     =     BasicTokenizer(do_lower_case=_SCREAMING_SNAKE_CASE)

								self.assertListEqual(
								    tokenizer.tokenize(""" \tHäLLo!how  \n Are yoU?  """)			,    ["""hallo""", """!""", """how""", """are""", """you""", """?"""])
								self.assertListEqual(tokenizer.tokenize("""H\u00E9llo""")			,    ["""hello"""])




		def 	_snake_case	(  self					:str)					->			List[Any]:






								'''simple docstring'''






								UpperCamelCase_     :	Dict					     =     BasicTokenizer(do_lower_case=_SCREAMING_SNAKE_CASE)

								self.assertListEqual(
								    tokenizer.tokenize(""" \tHeLLo!how  \n Are yoU?  """)			,    ["""HeLLo""", """!""", """how""", """Are""", """yoU""", """?"""])




		def 	_snake_case	(  self					:Tuple)					->			Optional[Any]:






								'''simple docstring'''






								UpperCamelCase_     :	int					     =     BasicTokenizer(do_lower_case=_SCREAMING_SNAKE_CASE			,    strip_accents=_SCREAMING_SNAKE_CASE)

								self.assertListEqual(
								    tokenizer.tokenize(""" \tHäLLo!how  \n Are yoU?  """)			,    ["""HäLLo""", """!""", """how""", """Are""", """yoU""", """?"""])




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






								'''simple docstring'''






								UpperCamelCase_     :	List[Any]					     =     BasicTokenizer(do_lower_case=_SCREAMING_SNAKE_CASE			,    strip_accents=_SCREAMING_SNAKE_CASE)

								self.assertListEqual(
								    tokenizer.tokenize(""" \tHäLLo!how  \n Are yoU?  """)			,    ["""HaLLo""", """!""", """how""", """Are""", """yoU""", """?"""])




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






								'''simple docstring'''






								UpperCamelCase_     :	str					     =     BasicTokenizer(do_lower_case=_SCREAMING_SNAKE_CASE			,    never_split=["""[UNK]"""])

								self.assertListEqual(
								    tokenizer.tokenize(""" \tHeLLo!how  \n Are yoU? [UNK]""")			,    ["""HeLLo""", """!""", """how""", """Are""", """yoU""", """?""", """[UNK]"""])




		def 	_snake_case	(  self					:str)					->			Optional[int]:






								'''simple docstring'''






								UpperCamelCase_     :	List[str]					     =     ["""[UNK]""", """[CLS]""", """[SEP]""", """want""", """##want""", """##ed""", """wa""", """un""", """runn""", """##ing"""]

								UpperCamelCase_     :	Optional[Any]					     =     {}
								for i, token in enumerate(_SCREAMING_SNAKE_CASE):
														UpperCamelCase_     :	int					     =     i
								UpperCamelCase_     :	Optional[int]					     =     WordpieceTokenizer(vocab=_SCREAMING_SNAKE_CASE			,    unk_token="""[UNK]""")

								self.assertListEqual(tokenizer.tokenize("""""")			,    [])

								self.assertListEqual(tokenizer.tokenize("""unwanted running""")			,    ["""un""", """##want""", """##ed""", """runn""", """##ing"""])

								self.assertListEqual(tokenizer.tokenize("""unwantedX running""")			,    ["""[UNK]""", """runn""", """##ing"""])




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






								'''simple docstring'''






								self.assertTrue(_is_whitespace(""" """))
								self.assertTrue(_is_whitespace("""\t"""))
								self.assertTrue(_is_whitespace("""\r"""))
								self.assertTrue(_is_whitespace("""\n"""))
								self.assertTrue(_is_whitespace("""\u00A0"""))

								self.assertFalse(_is_whitespace("""A"""))
								self.assertFalse(_is_whitespace("""-"""))




		def 	_snake_case	(  self					:Tuple)					->			Optional[Any]:






								'''simple docstring'''






								self.assertTrue(_is_control("""\u0005"""))

								self.assertFalse(_is_control("""A"""))
								self.assertFalse(_is_control(""" """))
								self.assertFalse(_is_control("""\t"""))
								self.assertFalse(_is_control("""\r"""))




		def 	_snake_case	(  self					:Tuple)					->			List[Any]:






								'''simple docstring'''






								self.assertTrue(_is_punctuation("""-"""))
								self.assertTrue(_is_punctuation("""$"""))
								self.assertTrue(_is_punctuation("""`"""))
								self.assertTrue(_is_punctuation("""."""))

								self.assertFalse(_is_punctuation("""A"""))
								self.assertFalse(_is_punctuation(""" """))




		def 	_snake_case	(  self					:Optional[int])					->			List[Any]:






								'''simple docstring'''






								UpperCamelCase_     :	Tuple					     =     self.get_tokenizer()

								# Example taken from the issue https://github.com/huggingface/tokenizers/issues/340
								self.assertListEqual([tokenizer.tokenize(_SCREAMING_SNAKE_CASE) for t in ["""Test""", """\xad""", """test"""]]			,    [["""[UNK]"""], [], ["""[UNK]"""]])

								if self.test_rust_tokenizer:
														UpperCamelCase_     :	Dict					     =     self.get_rust_tokenizer()
														self.assertListEqual(
														    [rust_tokenizer.tokenize(_SCREAMING_SNAKE_CASE) for t in ["""Test""", """\xad""", """test"""]]			,    [["""[UNK]"""], [], ["""[UNK]"""]])




		@slow
		def 	_snake_case	(  self					:int)					->			List[Any]:






								'''simple docstring'''






								UpperCamelCase_     :	Union[str, Any]					     =     self.tokenizer_class.from_pretrained("""bert-base-uncased""")

								UpperCamelCase_     :	int					     =     tokenizer.encode("""sequence builders"""			,    add_special_tokens=_SCREAMING_SNAKE_CASE)
								UpperCamelCase_     :	Optional[int]					     =     tokenizer.encode("""multi-sequence build"""			,    add_special_tokens=_SCREAMING_SNAKE_CASE)

								UpperCamelCase_     :	Optional[Any]					     =     tokenizer.build_inputs_with_special_tokens(_SCREAMING_SNAKE_CASE)
								UpperCamelCase_     :	Dict					     =     tokenizer.build_inputs_with_special_tokens(_SCREAMING_SNAKE_CASE			,    _SCREAMING_SNAKE_CASE)

								assert encoded_sentence == [1_0_1] + text + [1_0_2]
								assert encoded_pair == [1_0_1] + text + [1_0_2] + text_a + [1_0_2]




		def 	_snake_case	(  self					:Dict)					->			Tuple:






								'''simple docstring'''






								for tokenizer, pretrained_name, kwargs in self.tokenizers_list:
														with self.subTest(F"""{tokenizer.__class__.__name__} ({pretrained_name})"""):
																				UpperCamelCase_     :	Optional[int]					     =     self.rust_tokenizer_class.from_pretrained(_SCREAMING_SNAKE_CASE			,    **_SCREAMING_SNAKE_CASE)

																				UpperCamelCase_     :	List[Any]					     =     F"""A, naïve {tokenizer_r.mask_token} AllenNLP sentence."""
																				UpperCamelCase_     :	Optional[int]					     =     tokenizer_r.encode_plus(
																				    _SCREAMING_SNAKE_CASE			,    return_attention_mask=_SCREAMING_SNAKE_CASE			,    return_token_type_ids=_SCREAMING_SNAKE_CASE			,    return_offsets_mapping=_SCREAMING_SNAKE_CASE			,    add_special_tokens=_SCREAMING_SNAKE_CASE			,    )

																				UpperCamelCase_     :	Optional[int]					     =     tokenizer_r.do_lower_case if hasattr(_SCREAMING_SNAKE_CASE			,    """do_lower_case""") else False
																				UpperCamelCase_     :	List[str]					     =     (
																				    [
																				        ((0, 0), tokenizer_r.cls_token),
																				        ((0, 1), """A"""),
																				        ((1, 2), ""","""),
																				        ((3, 5), """na"""),
																				        ((5, 6), """##ï"""),
																				        ((6, 8), """##ve"""),
																				        ((9, 1_5), tokenizer_r.mask_token),
																				        ((1_6, 2_1), """Allen"""),
																				        ((2_1, 2_3), """##NL"""),
																				        ((2_3, 2_4), """##P"""),
																				        ((2_5, 3_3), """sentence"""),
																				        ((3_3, 3_4), """."""),
																				        ((0, 0), tokenizer_r.sep_token),
																				    ]
																				    if not do_lower_case
																				    else [
																				        ((0, 0), tokenizer_r.cls_token),
																				        ((0, 1), """a"""),
																				        ((1, 2), ""","""),
																				        ((3, 8), """naive"""),
																				        ((9, 1_5), tokenizer_r.mask_token),
																				        ((1_6, 2_1), """allen"""),
																				        ((2_1, 2_3), """##nl"""),
																				        ((2_3, 2_4), """##p"""),
																				        ((2_5, 3_3), """sentence"""),
																				        ((3_3, 3_4), """."""),
																				        ((0, 0), tokenizer_r.sep_token),
																				    ]
																				)

																				self.assertEqual(
																				    [e[1] for e in expected_results]			,    tokenizer_r.convert_ids_to_tokens(tokens["""input_ids"""]))
																				self.assertEqual([e[0] for e in expected_results]			,    tokens["""offset_mapping"""])





		@slow
		def 	_snake_case	(  self					:Any)					->			str:






								'''simple docstring'''






								for tokenizer, pretrained_name, kwargs in self.tokenizers_list:
														with self.subTest(F"""{tokenizer.__class__.__name__} ({pretrained_name})"""):
																				UpperCamelCase_     :	List[str]					     =     self.rust_tokenizer_class.from_pretrained(_SCREAMING_SNAKE_CASE			,    **_SCREAMING_SNAKE_CASE)
																				UpperCamelCase_     :	Union[str, Any]					     =     self.tokenizer_class.from_pretrained(_SCREAMING_SNAKE_CASE			,    **_SCREAMING_SNAKE_CASE)
																				UpperCamelCase_     :	Optional[int]					     =     [["""Hello world!""", """Nice to meet you!"""], ["""The cute cat.""", """The adorable dog."""]]

																				UpperCamelCase_     :	Union[str, Any]					     =     tokenizer_r.batch_encode_candidates(_SCREAMING_SNAKE_CASE			,    max_length=1_0			,    return_tensors="""np""")
																				UpperCamelCase_     :	List[str]					     =     tokenizer_p.batch_encode_candidates(_SCREAMING_SNAKE_CASE			,    max_length=1_0			,    return_tensors="""np""")

																				UpperCamelCase_     :	Union[str, Any]					     =     (2, 2, 1_0)

																				self.assertEqual(encoded_sentence_r["""input_ids"""].shape			,    _SCREAMING_SNAKE_CASE)
																				self.assertEqual(encoded_sentence_r["""attention_mask"""].shape			,    _SCREAMING_SNAKE_CASE)
																				self.assertEqual(encoded_sentence_r["""token_type_ids"""].shape			,    _SCREAMING_SNAKE_CASE)

																				self.assertEqual(encoded_sentence_p["""input_ids"""].shape			,    _SCREAMING_SNAKE_CASE)
																				self.assertEqual(encoded_sentence_p["""attention_mask"""].shape			,    _SCREAMING_SNAKE_CASE)
																				self.assertEqual(encoded_sentence_p["""token_type_ids"""].shape			,    _SCREAMING_SNAKE_CASE)




