

'''simple docstring'''







import gc
import unittest

from transformers import MODEL_FOR_MASKED_LM_MAPPING, TF_MODEL_FOR_MASKED_LM_MAPPING, FillMaskPipeline, pipeline
from transformers.pipelines import PipelineException
from transformers.testing_utils import (
    is_pipeline_test,
    is_torch_available,
    nested_simplify,
    require_tf,
    require_torch,
    require_torch_gpu,
    slow,
)

from .test_pipelines_common import ANY


@is_pipeline_test
class 					A__      (      unittest.TestCase			):
    lowercase						=		MODEL_FOR_MASKED_LM_MAPPING
    lowercase						=		TF_MODEL_FOR_MASKED_LM_MAPPING



    def 					snake_case_			(					self       )						->      int:





           '''simple docstring'''
           super().tearDown()
           # clean-up as much as possible GPU memory occupied by PyTorch
           gc.collect()
           if is_torch_available():
                  import torch

                  torch.cuda.empty_cache()



    @require_tf
    def 					snake_case_			(					self       )						->      Optional[int]:





           '''simple docstring'''
           A_						=      pipeline(task="""fill-mask"""		,				model="""sshleifer/tiny-distilroberta-base"""		,				top_k=2		,				framework="""tf"""       )
           A_						=      unmasker("""My name is <mask>"""       )
           self.assertEqual(
               nested_simplify(UpperCamelCase__		,				decimals=6       )		,				[
                   {"""sequence""": """My name is grouped""", """score""": 2.1e-0_5, """token""": 38015, """token_str""": """ grouped"""},
                   {"""sequence""": """My name is accuser""", """score""": 2.1e-0_5, """token""": 25506, """token_str""": """ accuser"""},
               ]		,				)

           A_						=      unmasker("""The largest city in France is <mask>"""       )
           self.assertEqual(
               nested_simplify(UpperCamelCase__		,				decimals=6       )		,				[
                   {
                       """sequence""": """The largest city in France is grouped""",
                       """score""": 2.1e-0_5,
                       """token""": 38015,
                       """token_str""": """ grouped""",
                   },
                   {
                       """sequence""": """The largest city in France is accuser""",
                       """score""": 2.1e-0_5,
                       """token""": 25506,
                       """token_str""": """ accuser""",
                   },
               ]		,				)

           A_						=      unmasker("""My name is <mask>"""		,				targets=[""" Patrick""", """ Clara""", """ Teven"""]		,				top_k=3       )
           self.assertEqual(
               nested_simplify(UpperCamelCase__		,				decimals=6       )		,				[
                   {"""sequence""": """My name is Clara""", """score""": 2e-0_5, """token""": 13606, """token_str""": """ Clara"""},
                   {"""sequence""": """My name is Patrick""", """score""": 2e-0_5, """token""": 3499, """token_str""": """ Patrick"""},
                   {"""sequence""": """My name is Te""", """score""": 1.9e-0_5, """token""": 2941, """token_str""": """ Te"""},
               ]		,				)



    @require_torch
    def 					snake_case_			(					self       )						->      int:





           '''simple docstring'''
           A_						=      pipeline(task="""fill-mask"""		,				model="""sshleifer/tiny-distilroberta-base"""		,				top_k=2		,				framework="""pt"""       )

           A_						=      unmasker("""My name is <mask>"""       )
           self.assertEqual(
               nested_simplify(UpperCamelCase__		,				decimals=6       )		,				[
                   {"""sequence""": """My name is Maul""", """score""": 2.2e-0_5, """token""": 35676, """token_str""": """ Maul"""},
                   {"""sequence""": """My name isELS""", """score""": 2.2e-0_5, """token""": 16416, """token_str""": """ELS"""},
               ]		,				)

           A_						=      unmasker("""The largest city in France is <mask>"""       )
           self.assertEqual(
               nested_simplify(UpperCamelCase__		,				decimals=6       )		,				[
                   {
                       """sequence""": """The largest city in France is Maul""",
                       """score""": 2.2e-0_5,
                       """token""": 35676,
                       """token_str""": """ Maul""",
                   },
                   {"""sequence""": """The largest city in France isELS""", """score""": 2.2e-0_5, """token""": 16416, """token_str""": """ELS"""},
               ]		,				)

           A_						=      unmasker("""My name is <mask>"""		,				targets=[""" Patrick""", """ Clara""", """ Teven"""]		,				top_k=3       )
           self.assertEqual(
               nested_simplify(UpperCamelCase__		,				decimals=6       )		,				[
                   {"""sequence""": """My name is Patrick""", """score""": 2.1e-0_5, """token""": 3499, """token_str""": """ Patrick"""},
                   {"""sequence""": """My name is Te""", """score""": 2e-0_5, """token""": 2941, """token_str""": """ Te"""},
                   {"""sequence""": """My name is Clara""", """score""": 2e-0_5, """token""": 13606, """token_str""": """ Clara"""},
               ]		,				)

           A_						=      unmasker("""My name is <mask> <mask>"""		,				top_k=2       )

           self.assertEqual(
               nested_simplify(UpperCamelCase__		,				decimals=6       )		,				[
                   [
                       {
                           """score""": 2.2e-0_5,
                           """token""": 35676,
                           """token_str""": """ Maul""",
                           """sequence""": """<s>My name is Maul<mask></s>""",
                       },
                       {"""score""": 2.2e-0_5, """token""": 16416, """token_str""": """ELS""", """sequence""": """<s>My name isELS<mask></s>"""},
                   ],
                   [
                       {
                           """score""": 2.2e-0_5,
                           """token""": 35676,
                           """token_str""": """ Maul""",
                           """sequence""": """<s>My name is<mask> Maul</s>""",
                       },
                       {"""score""": 2.2e-0_5, """token""": 16416, """token_str""": """ELS""", """sequence""": """<s>My name is<mask>ELS</s>"""},
                   ],
               ]		,				)



    @require_torch_gpu
    def 					snake_case_			(					self       )						->      List[str]:





           '''simple docstring'''
           A_						=      pipeline("""fill-mask"""		,				model="""hf-internal-testing/tiny-random-distilbert"""		,				device=0		,				framework="""pt"""       )

           # convert model to fp16
           pipe.model.half()

           A_						=      pipe("""Paris is the [MASK] of France."""       )
           # We actually don't care about the result, we just want to make sure
           # it works, meaning the float16 tensor got casted back to float32
           # for postprocessing.
           self.assertIsInstance(UpperCamelCase__		,				UpperCamelCase__       )



    @slow
    @require_torch
    def 					snake_case_			(					self       )						->      int:





           '''simple docstring'''
           A_						=      pipeline(task="""fill-mask"""		,				model="""distilroberta-base"""		,				top_k=2		,				framework="""pt"""       )
           self.run_large_test(UpperCamelCase__       )



    @slow
    @require_tf
    def 					snake_case_			(					self       )						->      Optional[int]:





           '''simple docstring'''
           A_						=      pipeline(task="""fill-mask"""		,				model="""distilroberta-base"""		,				top_k=2		,				framework="""tf"""       )
           self.run_large_test(UpperCamelCase__       )



    def 					snake_case_			(					self		,				UpperCamelCase__       )						->      Optional[int]:





           '''simple docstring'''
           A_						=      unmasker("""My name is <mask>"""       )
           self.assertEqual(
               nested_simplify(UpperCamelCase__       )		,				[
                   {"""sequence""": """My name is John""", """score""": 0.008, """token""": 610, """token_str""": """ John"""},
                   {"""sequence""": """My name is Chris""", """score""": 0.007, """token""": 1573, """token_str""": """ Chris"""},
               ]		,				)
           A_						=      unmasker("""The largest city in France is <mask>"""       )
           self.assertEqual(
               nested_simplify(UpperCamelCase__       )		,				[
                   {
                       """sequence""": """The largest city in France is Paris""",
                       """score""": 0.251,
                       """token""": 2201,
                       """token_str""": """ Paris""",
                   },
                   {
                       """sequence""": """The largest city in France is Lyon""",
                       """score""": 0.214,
                       """token""": 12790,
                       """token_str""": """ Lyon""",
                   },
               ]		,				)

           A_						=      unmasker("""My name is <mask>"""		,				targets=[""" Patrick""", """ Clara""", """ Teven"""]		,				top_k=3       )
           self.assertEqual(
               nested_simplify(UpperCamelCase__       )		,				[
                   {"""sequence""": """My name is Patrick""", """score""": 0.005, """token""": 3499, """token_str""": """ Patrick"""},
                   {"""sequence""": """My name is Clara""", """score""": 0.000, """token""": 13606, """token_str""": """ Clara"""},
                   {"""sequence""": """My name is Te""", """score""": 0.000, """token""": 2941, """token_str""": """ Te"""},
               ]		,				)



    @require_torch
    def 					snake_case_			(					self       )						->      Any:





           '''simple docstring'''
           A_						=      pipeline(task="""fill-mask"""		,				model="""sshleifer/tiny-distilroberta-base"""		,				framework="""pt"""       )
           A_						=      None
           A_						=      None
           self.run_pipeline_test(UpperCamelCase__		,				[]       )



    @require_tf
    def 					snake_case_			(					self       )						->      Dict:





           '''simple docstring'''
           A_						=      pipeline(task="""fill-mask"""		,				model="""sshleifer/tiny-distilroberta-base"""		,				framework="""tf"""       )
           A_						=      None
           A_						=      None
           self.run_pipeline_test(UpperCamelCase__		,				[]       )



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





           '''simple docstring'''

           if tokenizer is None or tokenizer.mask_token_id is None:
                  self.skipTest("""The provided tokenizer has no mask token, (probably reformer or wav2vec2)"""       )

           A_						=      FillMaskPipeline(model=UpperCamelCase__		,				tokenizer=UpperCamelCase__       )
           A_						=      [
               f'''This is another {tokenizer.mask_token} test''',
           ]
           return fill_masker, examples



    def 					snake_case_			(					self		,				UpperCamelCase__		,				UpperCamelCase__       )						->      Optional[int]:





           '''simple docstring'''
           A_						=      fill_masker.tokenizer
           A_						=      fill_masker.model

           A_						=      fill_masker(
               f'''This is a {tokenizer.mask_token}'''		,				)
           self.assertEqual(
               UpperCamelCase__		,				[
                   {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                   {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                   {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                   {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                   {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
               ]		,				)

           A_						=      fill_masker([f'''This is a {tokenizer.mask_token}''']       )
           self.assertEqual(
               UpperCamelCase__		,				[
                   {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                   {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                   {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                   {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                   {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
               ]		,				)

           A_						=      fill_masker([f'''This is a {tokenizer.mask_token}''', f'''Another {tokenizer.mask_token} great test.''']       )
           self.assertEqual(
               UpperCamelCase__		,				[
                   [
                       {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                       {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                       {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                       {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                       {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                   ],
                   [
                       {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                       {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                       {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                       {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                       {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                   ],
               ]		,				)

           with self.assertRaises(UpperCamelCase__       ):
                  fill_masker([None]       )
           # No mask_token is not supported
           with self.assertRaises(UpperCamelCase__       ):
                  fill_masker("""This is"""       )

           self.run_test_top_k(UpperCamelCase__		,				UpperCamelCase__       )
           self.run_test_targets(UpperCamelCase__		,				UpperCamelCase__       )
           self.run_test_top_k_targets(UpperCamelCase__		,				UpperCamelCase__       )
           self.fill_mask_with_duplicate_targets_and_top_k(UpperCamelCase__		,				UpperCamelCase__       )
           self.fill_mask_with_multiple_masks(UpperCamelCase__		,				UpperCamelCase__       )



    def 					snake_case_			(					self		,				UpperCamelCase__		,				UpperCamelCase__       )						->      str:





           '''simple docstring'''
           A_						=      tokenizer.get_vocab()
           A_						=      sorted(vocab.keys()       )[:2]
           # Pipeline argument
           A_						=      FillMaskPipeline(model=UpperCamelCase__		,				tokenizer=UpperCamelCase__		,				targets=UpperCamelCase__       )
           A_						=      fill_masker(f'''This is a {tokenizer.mask_token}'''       )
           self.assertEqual(
               UpperCamelCase__		,				[
                   {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                   {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
               ]		,				)
           A_						=      {vocab[el] for el in targets}
           self.assertEqual({el["""token"""] for el in outputs}		,				UpperCamelCase__       )
           A_						=      [tokenizer.decode([x]       ) for x in target_ids]
           self.assertEqual({el["""token_str"""] for el in outputs}		,				set(UpperCamelCase__       )       )

           # Call argument
           A_						=      FillMaskPipeline(model=UpperCamelCase__		,				tokenizer=UpperCamelCase__       )
           A_						=      fill_masker(f'''This is a {tokenizer.mask_token}'''		,				targets=UpperCamelCase__       )
           self.assertEqual(
               UpperCamelCase__		,				[
                   {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                   {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
               ]		,				)
           A_						=      {vocab[el] for el in targets}
           self.assertEqual({el["""token"""] for el in outputs}		,				UpperCamelCase__       )
           A_						=      [tokenizer.decode([x]       ) for x in target_ids]
           self.assertEqual({el["""token_str"""] for el in outputs}		,				set(UpperCamelCase__       )       )

           # Score equivalence
           A_						=      fill_masker(f'''This is a {tokenizer.mask_token}'''		,				targets=UpperCamelCase__       )
           A_						=      [top_mask["""token_str"""] for top_mask in outputs]
           A_						=      [top_mask["""score"""] for top_mask in outputs]

           # For some BPE tokenizers, `</w>` is removed during decoding, so `token_str` won't be the same as in `targets`.
           if set(UpperCamelCase__       ) == set(UpperCamelCase__       ):
                  A_						=      fill_masker(f'''This is a {tokenizer.mask_token}'''		,				targets=UpperCamelCase__       )
                  A_						=      [top_mask["""score"""] for top_mask in unmasked_targets]
                  self.assertEqual(nested_simplify(UpperCamelCase__       )		,				nested_simplify(UpperCamelCase__       )       )

           # Raises with invalid
           with self.assertRaises(UpperCamelCase__       ):
                  A_						=      fill_masker(f'''This is a {tokenizer.mask_token}'''		,				targets=[]       )
           # For some tokenizers, `""` is actually in the vocabulary and the expected error won't raised
           if "" not in tokenizer.get_vocab():
                  with self.assertRaises(UpperCamelCase__       ):
                         A_						=      fill_masker(f'''This is a {tokenizer.mask_token}'''		,				targets=[""""""]       )
                  with self.assertRaises(UpperCamelCase__       ):
                         A_						=      fill_masker(f'''This is a {tokenizer.mask_token}'''		,				targets=""""""       )



    def 					snake_case_			(					self		,				UpperCamelCase__		,				UpperCamelCase__       )						->      List[Any]:





           '''simple docstring'''
           A_						=      FillMaskPipeline(model=UpperCamelCase__		,				tokenizer=UpperCamelCase__		,				top_k=2       )
           A_						=      fill_masker(f'''This is a {tokenizer.mask_token}'''       )
           self.assertEqual(
               UpperCamelCase__		,				[
                   {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                   {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
               ]		,				)

           A_						=      FillMaskPipeline(model=UpperCamelCase__		,				tokenizer=UpperCamelCase__       )
           A_						=      fill_masker(f'''This is a {tokenizer.mask_token}'''		,				top_k=2       )
           self.assertEqual(
               UpperCamelCase__		,				[
                   {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                   {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
               ]		,				)
           self.assertEqual(nested_simplify(UpperCamelCase__       )		,				nested_simplify(UpperCamelCase__       )       )



    def 					snake_case_			(					self		,				UpperCamelCase__		,				UpperCamelCase__       )						->      Tuple:





           '''simple docstring'''
           A_						=      tokenizer.get_vocab()
           A_						=      FillMaskPipeline(model=UpperCamelCase__		,				tokenizer=UpperCamelCase__       )

           # top_k=2, ntargets=3
           A_						=      sorted(vocab.keys()       )[:3]
           A_						=      fill_masker(f'''This is a {tokenizer.mask_token}'''		,				top_k=2		,				targets=UpperCamelCase__       )

           # If we use the most probably targets, and filter differently, we should still
           # have the same results
           A_						=      [el["""token_str"""] for el in sorted(UpperCamelCase__		,				key=lambda UpperCamelCase__       : x["score"]		,				reverse=UpperCamelCase__       )]
           # For some BPE tokenizers, `</w>` is removed during decoding, so `token_str` won't be the same as in `targets`.
           if set(UpperCamelCase__       ).issubset(UpperCamelCase__       ):
                  A_						=      fill_masker(f'''This is a {tokenizer.mask_token}'''		,				top_k=3		,				targets=UpperCamelCase__       )
                  # They should yield exactly the same result
                  self.assertEqual(nested_simplify(UpperCamelCase__       )		,				nested_simplify(UpperCamelCase__       )       )



    def 					snake_case_			(					self		,				UpperCamelCase__		,				UpperCamelCase__       )						->      int:





           '''simple docstring'''
           A_						=      FillMaskPipeline(model=UpperCamelCase__		,				tokenizer=UpperCamelCase__       )
           A_						=      tokenizer.get_vocab()
           # String duplicates + id duplicates
           A_						=      sorted(vocab.keys()       )[:3]
           A_						=      [targets[0], targets[1], targets[0], targets[2], targets[1]]
           A_						=      fill_masker(f'''My name is {tokenizer.mask_token}'''		,				targets=UpperCamelCase__		,				top_k=10       )

           # The target list contains duplicates, so we can't output more
           # than them
           self.assertEqual(len(UpperCamelCase__       )		,				3       )







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





           '''simple docstring'''
           A_						=      FillMaskPipeline(model=UpperCamelCase__		,				tokenizer=UpperCamelCase__       )

           A_						=      fill_masker(
               f'''This is a {tokenizer.mask_token} {tokenizer.mask_token} {tokenizer.mask_token}'''		,				top_k=2       )
           self.assertEqual(
               UpperCamelCase__		,				[
                   [
                       {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                       {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                   ],
                   [
                       {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                       {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                   ],
                   [
                       {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                       {"""sequence""": ANY(UpperCamelCase__       ), """score""": ANY(UpperCamelCase__       ), """token""": ANY(UpperCamelCase__       ), """token_str""": ANY(UpperCamelCase__       )},
                   ],
               ]		,				)



'''simple docstring'''







__lowerCamelCase		       =    range(2, 20 + 1)
__lowerCamelCase		       =    [10**k for k in range(ks[-1] + 1)]
__lowerCamelCase		       =    {}
def       UpperCAmelCase__    (      UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__				)			->			Tuple:
       A_						=      sum(a_i[j] for j in range(UpperCAmelCase__,       len(UpperCAmelCase__				)				)				)
       A_						=      sum(a_i[j] * base[j] for j in range(min(len(UpperCAmelCase__				),       UpperCAmelCase__				)				)				)

       A_					,			A_						=      0, 0
       A_						=      n - i

       A_						=      memo.get(UpperCAmelCase__				)

       if sub_memo is not None:
              A_						=      sub_memo.get(UpperCAmelCase__				)

              if jumps is not None and len(UpperCAmelCase__				) > 0:
                     # find and make the largest jump without going over
                     A_						=      -1
                     for _k in range(len(UpperCAmelCase__				) - 1,       -1,       -1				):
                            if jumps[_k][2] <= k and jumps[_k][1] <= max_dn:
                                   A_						=      _k
                                   break

                     if max_jump >= 0:
                            A_					,			A_					,			A_						=      jumps[max_jump]
                            # since the difference between jumps is cached, add c
                            A_						=      diff + c
                            for j in range(min(UpperCAmelCase__,       len(UpperCAmelCase__				)				)				):
                                   A_					,			A_						=      divmod(UpperCAmelCase__,       10				)
                            if new_c > 0:
                                   add(UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__				)

              else:
                     A_						=      []
       else:
              A_						=      {c: []}
              A_						=      sub_memo

       if dn >= max_dn or c + diff >= base[k]:
              return diff, dn

       if k > ks[0]:
              while True:
                     # keep doing smaller jumps
                     A_					,			A_						=      next_term(UpperCAmelCase__,       k - 1,       i + dn,       UpperCAmelCase__				)
                     diff += _diff
                     dn += terms_jumped

                     if dn >= max_dn or c + diff >= base[k]:
                            break
       else:
              # would be too small a jump, just compute sequential terms instead
              A_					,			A_						=      compute(UpperCAmelCase__,       UpperCAmelCase__,       i + dn,       UpperCAmelCase__				)
              diff += _diff
              dn += terms_jumped

       A_						=      sub_memo[c]

       # keep jumps sorted by # of terms skipped
       A_						=      0
       while j < len(UpperCAmelCase__				):
              if jumps[j][1] > dn:
                     break
              j += 1

       # cache the jump for this value digitsum(b) and c
       sub_memo[c].insert(UpperCAmelCase__,       (diff, dn, k)				)
       return (diff, dn)
def       UpperCAmelCase__    (      UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__				)			->			int:
       if i >= n:
              return 0, i
       if k > len(UpperCAmelCase__				):
              a_i.extend([0 for _ in range(k - len(UpperCAmelCase__				)				)]				)

       # note: a_i -> b * 10^k + c
       # ds_b -> digitsum(b)
       # ds_c -> digitsum(c)
       A_						=      i
       A_					,			A_					,			A_						=      0, 0, 0
       for j in range(len(UpperCAmelCase__				)				):
              if j >= k:
                     ds_b += a_i[j]
              else:
                     ds_c += a_i[j]

       while i < n:
              i += 1
              A_						=      ds_c + ds_b
              diff += addend
              A_						=      0
              for j in range(UpperCAmelCase__				):
                     A_						=      a_i[j] + addend
                     A_					,			A_						=      divmod(UpperCAmelCase__,       10				)

                     ds_c += a_i[j]

              if addend > 0:
                     break

       if addend > 0:
              add(UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__				)
       return diff, i - start_i
def       UpperCAmelCase__    (      UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__				)			->			str:
       for j in range(UpperCAmelCase__,       len(UpperCAmelCase__				)				):
              A_						=      digits[j] + addend
              if s >= 10:
                     A_					,			A_						=      divmod(UpperCAmelCase__,       10				)
                     A_						=      addend // 10 + quotient
              else:
                     A_						=      s
                     A_						=      addend // 10

              if addend == 0:
                     break

       while addend > 0:
              A_					,			A_						=      divmod(UpperCAmelCase__,       10				)
              digits.append(UpperCAmelCase__				)
def       UpperCAmelCase__    (      UpperCAmelCase__ = 10**15				)			->			int:
       A_						=      [1]
       A_						=      1
       A_						=      0
       while True:
              A_					,			A_						=      next_term(UpperCAmelCase__,       20,       i + dn,       UpperCAmelCase__				)
              dn += terms_jumped
              if dn == n - i:
                     break

       A_						=      0
       for j in range(len(UpperCAmelCase__				)				):
              a_n += digits[j] * 10**j
       return a_n


if __name__ == "__main__":
      print(f"""{solution() = }""")
