



'''simple docstring'''

from __future__ import annotations

import random
import unittest

from transformers import TransfoXLConfig, is_tf_available
from transformers.testing_utils import require_tf, slow

from ...test_configuration_common import ConfigTester
from ...test_modeling_tf_common import TFModelTesterMixin, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_tf_available():
							import tensorflow as tf

							from transformers import (
							    TF_TRANSFO_XL_PRETRAINED_MODEL_ARCHIVE_LIST,
							    TFTransfoXLForSequenceClassification,
							    TFTransfoXLLMHeadModel,
							    TFTransfoXLModel,
							)

class      __magic_name__						:







							def __init__(							self :	str     ,_UpperCAmelCase :	int     ,):
									_a					:				List[str]				=							parent
									_a					:				str				=							13
									_a					:				Tuple				=							7
									_a					:				Optional[Any]				=							30
									_a					:				str				=							self.seq_length + self.mem_len
									_a					:				Union[str, Any]				=							15
									_a					:				int				=							True
									_a					:				List[str]				=							True
									_a					:				Optional[int]				=							99
									_a					:				Optional[int]				=							[10, 50, 80]
									_a					:				Optional[int]				=							32
									_a					:				Union[str, Any]				=							32
									_a					:				Any				=							4
									_a					:				Optional[int]				=							8
									_a					:				Any				=							128
									_a					:				Dict				=							2
									_a					:				List[Any]				=							2
									_a					:				Dict				=							None
									_a					:				int				=							1
									_a					:				Optional[int]				=							0
									_a					:				List[Any]				=							3
									_a					:				Dict				=							self.vocab_size - 1
									_a					:				Tuple				=							0.01







							def 							__lowercase      (							self :	List[str]		):
									_a					:				Tuple				=							ids_tensor([self.batch_size, self.seq_length]     ,self.vocab_size		)
									_a					:				List[Any]				=							ids_tensor([self.batch_size, self.seq_length]     ,self.vocab_size		)

									_a					:				Tuple				=							None
									if self.use_labels:
											_a					:				Dict				=							ids_tensor([self.batch_size, self.seq_length]     ,self.vocab_size		)

									_a					:				str				=							TransfoXLConfig(
									    vocab_size=self.vocab_size     ,mem_len=self.mem_len     ,clamp_len=self.clamp_len     ,cutoffs=self.cutoffs     ,d_model=self.hidden_size     ,d_embed=self.d_embed     ,n_head=self.num_attention_heads     ,d_head=self.d_head     ,d_inner=self.d_inner     ,div_val=self.div_val     ,n_layer=self.num_hidden_layers     ,eos_token_id=self.eos_token_id     ,pad_token_id=self.vocab_size - 1     ,init_range=self.init_range     ,num_labels=self.num_labels     ,)

									return (config, input_ids_a, input_ids_a, lm_labels)







							def 							__lowercase      (							self :	Optional[Any]		):
									random.seed(self.seed		)
									tf.random.set_seed(self.seed		)







							def 							__lowercase      (							self :	List[str]     ,_UpperCAmelCase :	Optional[int]     ,_UpperCAmelCase :	Any     ,_UpperCAmelCase :	Dict     ,_UpperCAmelCase :	List[str]		):
									_a					:				Optional[int]				=							TFTransfoXLModel(lowerCamelCase_		)

									_a					:				str				=							model(lowerCamelCase_		).to_tuple()

									_a					:				Dict				=							{"""input_ids""": input_ids_a, """mems""": mems_a}

									_a					:				List[str]				=							model(lowerCamelCase_		).to_tuple()

									self.parent.assertEqual(hidden_states_a.shape     ,(self.batch_size, self.seq_length, self.hidden_size)		)
									self.parent.assertEqual(hidden_states_a.shape     ,(self.batch_size, self.seq_length, self.hidden_size)		)
									self.parent.assertListEqual(
									    [mem.shape for mem in mems_a]     ,[(self.mem_len, self.batch_size, self.hidden_size)] * self.num_hidden_layers     ,)
									self.parent.assertListEqual(
									    [mem.shape for mem in mems_a]     ,[(self.mem_len, self.batch_size, self.hidden_size)] * self.num_hidden_layers     ,)







							def 							__lowercase      (							self :	Union[str, Any]     ,_UpperCAmelCase :	Dict     ,_UpperCAmelCase :	List[Any]     ,_UpperCAmelCase :	Any     ,_UpperCAmelCase :	List[Any]		):
									_a					:				Tuple				=							TFTransfoXLLMHeadModel(lowerCamelCase_		)

									_a					:				Dict				=							model(lowerCamelCase_		).to_tuple()

									_a					:				Union[str, Any]				=							{"""input_ids""": input_ids_a, """labels""": lm_labels}
									_a					:				List[str]				=							model(lowerCamelCase_		).to_tuple()

									_a					:				Optional[Any]				=							model([input_ids_a, mems_a]		).to_tuple()

									_a					:				List[str]				=							{"""input_ids""": input_ids_a, """mems""": mems_a, """labels""": lm_labels}

									_a					:				int				=							model(lowerCamelCase_		).to_tuple()

									self.parent.assertEqual(lm_logits_a.shape     ,(self.batch_size, self.seq_length, self.vocab_size)		)
									self.parent.assertListEqual(
									    [mem.shape for mem in mems_a]     ,[(self.mem_len, self.batch_size, self.hidden_size)] * self.num_hidden_layers     ,)

									self.parent.assertEqual(lm_logits_a.shape     ,(self.batch_size, self.seq_length, self.vocab_size)		)
									self.parent.assertListEqual(
									    [mem.shape for mem in mems_a]     ,[(self.mem_len, self.batch_size, self.hidden_size)] * self.num_hidden_layers     ,)







							def 							__lowercase      (							self :	Tuple     ,_UpperCAmelCase :	Union[str, Any]     ,_UpperCAmelCase :	Optional[Any]     ,_UpperCAmelCase :	Any     ,_UpperCAmelCase :	str		):
									_a					:				Any				=							TFTransfoXLForSequenceClassification(lowerCamelCase_		)
									_a					:				int				=							model(lowerCamelCase_		)
									self.parent.assertEqual(result.logits.shape     ,(self.batch_size, self.num_labels)		)







							def 							__lowercase      (							self :	int		):
									_a					:				str				=							self.prepare_config_and_inputs()
									(_a)					:				Any				=							config_and_inputs
									_a					:				Optional[int]				=							{"""input_ids""": input_ids_a}
									return config, inputs_dict



@require_tf
class      __magic_name__						(   __snake_case      ,						__snake_case      ,						unittest.TestCase       ):
							lowerCAmelCase	:   Optional[int]           = (
							    (TFTransfoXLModel, TFTransfoXLLMHeadModel, TFTransfoXLForSequenceClassification) if is_tf_available() else ()
							)
							lowerCAmelCase	:   int           = () if is_tf_available() else ()
							lowerCAmelCase	:   List[Any]           = (
							    {
							        "feature-extraction": TFTransfoXLModel,
							        "text-classification": TFTransfoXLForSequenceClassification,
							        "text-generation": TFTransfoXLLMHeadModel,
							        "zero-shot": TFTransfoXLForSequenceClassification,
							    }
							    if is_tf_available()
							    else {}
							)
							# TODO: add this test when TFTransfoXLLMHead has a linear output layer implemented
							lowerCAmelCase	:   str           = False
							lowerCAmelCase	:   Optional[int]           = False
							lowerCAmelCase	:   str           = False
							lowerCAmelCase	:   str           = False







							def 							__lowercase      (							self :	str     ,_UpperCAmelCase :	int     ,_UpperCAmelCase :	Optional[Any]     ,_UpperCAmelCase :	str     ,_UpperCAmelCase :	Any     ,_UpperCAmelCase :	Any		):
									if pipeline_test_casse_name == "TextGenerationPipelineTests":
											# Get `ValueError: AttributeError: 'NoneType' object has no attribute 'new_ones'` or `AssertionError`.
											# `TransfoXLConfig` was never used in pipeline tests: cannot create a simple
											# tokenizer.
											return True

									return False







							def 							__lowercase      (							self :	Union[str, Any]		):
									_a					:				Union[str, Any]				=							TFTransfoXLModelTester(self		)
									_a					:				int				=							ConfigTester(self     ,config_class=lowerCamelCase_     ,d_embed=37		)







							def 							__lowercase      (							self :	int		):
									self.config_tester.run_common_tests()







							def 							__lowercase      (							self :	List[str]		):
									self.model_tester.set_seed()
									_a					:				int				=							self.model_tester.prepare_config_and_inputs()
									self.model_tester.create_and_check_transfo_xl_model(*lowerCamelCase_		)







							def 							__lowercase      (							self :	str		):
									self.model_tester.set_seed()
									_a					:				str				=							self.model_tester.prepare_config_and_inputs()
									self.model_tester.create_and_check_transfo_xl_lm_head(*lowerCamelCase_		)







							def 							__lowercase      (							self :	Tuple		):
									_a					:				List[str]				=							self.model_tester.prepare_config_and_inputs()
									self.model_tester.create_and_check_transfo_xl_for_sequence_classification(*lowerCamelCase_		)







							def 							__lowercase      (							self :	int		):
									_a					:				Union[str, Any]				=							self.model_tester.prepare_config_and_inputs_for_common()
									_a					:				List[str]				=							[TFTransfoXLForSequenceClassification]

									for model_class in self.all_model_classes:
											_a					:				List[Any]				=							model_class(lowerCamelCase_		)
											assert isinstance(model.get_input_embeddings()     ,tf.keras.layers.Layer		)
											if model_class in list_other_models_with_output_ebd:
													_a					:				Dict				=							model.get_output_embeddings()
													assert isinstance(lowerCamelCase_     ,tf.keras.layers.Layer		)
													_a					:				Union[str, Any]				=							model.get_bias()
													assert name is None
											else:
													_a					:				Union[str, Any]				=							model.get_output_embeddings()
													assert x is None
													_a					:				Optional[int]				=							model.get_bias()
													assert name is None







							def 							__lowercase      (							self :	Dict		):
									# TODO JP: Make TransfoXL XLA compliant
									pass







							@slow
							def 							__lowercase      (							self :	Dict		):
									for model_name in TF_TRANSFO_XL_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
											_a					:				List[Any]				=							TFTransfoXLModel.from_pretrained(lowerCamelCase_		)
											self.assertIsNotNone(lowerCamelCase_		)







							@unittest.skip(reason='This model doesn\'t play well with fit() due to not returning a single loss.'		)
							def 							__lowercase      (							self :	Union[str, Any]		):
									pass



@require_tf
class      __magic_name__						(   unittest.TestCase       ):







							@unittest.skip('Skip test until #12651 is resolved.'		)
							@slow
							def 							__lowercase      (							self :	str		):
									_a					:				Optional[int]				=							TFTransfoXLLMHeadModel.from_pretrained('transfo-xl-wt103'		)
									# fmt: off
									_a					:				int				=							tf.convert_to_tensor([[33,1297,2,1,1009,4,1109,11739,4762,358,5,25,245,22,1706,17,20098,5,3215,21,37,1110,3,13,1041,4,24,603,490,2,71477,20098,104447,2,20961,1,2604,4,1,329,3,6224,831,16002,2,8,603,78967,29546,23,803,20,25,416,5,8,232,4,277,6,1855,4601,3,29546,54,8,3609,5,57211,49,4,1,277,18,8,1755,15691,3,341,25,416,693,42573,71,17,401,94,31,17919,2,29546,7873,18,1,435,23,11011,755,5,5167,3,7983,98,84,2,29546,3267,8,3609,4,1,4865,1075,2,6087,71,6,346,8,5854,3,29546,824,1400,1868,2,19,160,2,311,8,5496,2,20920,17,25,15097,3,24,24,0]]     ,dtype=tf.intaa		)  # noqa: E231
									# fmt: on
									#  In 1991 , the remains of Russian Tsar Nicholas II and his family
									#  ( except for Alexei and Maria ) are discovered .
									#  The voice of Nicholas's young son , Tsarevich Alexei Nikolaevich , narrates the
									#  remainder of the story . 1883 Western Siberia ,
									#  a young Grigori Rasputin is asked by his father and a group of men to perform magic .
									#  Rasputin has a vision and denounces one of the men as a horse thief . Although his
									#  father initially slaps him for making such an accusation , Rasputin watches as the
									#  man is chased outside and beaten . Twenty years later , Rasputin sees a vision of
									#  the Virgin Mary , prompting him to become a priest . Rasputin quickly becomes famous ,
									#  with people , even a bishop , begging for his blessing . <eod> </s> <eos>

									# fmt: off
									_a					:				Union[str, Any]				=							[33,1297,2,1,1009,4,1109,11739,4762,358,5,25,245,22,1706,17,20098,5,3215,21,37,1110,3,13,1041,4,24,603,490,2,71477,20098,104447,2,20961,1,2604,4,1,329,3,6224,831,16002,2,8,603,78967,29546,23,803,20,25,416,5,8,232,4,277,6,1855,4601,3,29546,54,8,3609,5,57211,49,4,1,277,18,8,1755,15691,3,341,25,416,693,42573,71,17,401,94,31,17919,2,29546,7873,18,1,435,23,11011,755,5,5167,3,7983,98,84,2,29546,3267,8,3609,4,1,4865,1075,2,6087,71,6,346,8,5854,3,29546,824,1400,1868,2,19,160,2,311,8,5496,2,20920,17,25,15097,3,24,24,0,33,1,1857,2,1,1009,4,1109,11739,4762,358,5,25,245,28,1110,3,13,1041,4,24,603,490,2,71477,20098,104447,2,20961,1,2604,4,1,329,3,0]  # noqa: E231
									# fmt: on
									#  In 1991, the remains of Russian Tsar Nicholas II and his family (
									#  except for Alexei and Maria ) are discovered. The voice of young son,
									#  Tsarevich Alexei Nikolaevich, narrates the remainder of the story.
									#  1883 Western Siberia, a young Grigori Rasputin is asked by his father
									#  and a group of men to perform magic. Rasputin has a vision and
									#  denounces one of the men as a horse thief. Although his father initially
									#  slaps him for making such an accusation, Rasputin watches as the man
									#  is chased outside and beaten. Twenty years later, Rasputin sees a vision
									#  of the Virgin Mary, prompting him to become a priest.
									#  Rasputin quickly becomes famous, with people, even a bishop, begging for
									#  his blessing. <unk> <unk> <eos> In the 1990s, the remains of Russian Tsar
									# Nicholas II and his family were discovered. The voice of <unk> young son,
									# Tsarevich Alexei Nikolaevich, narrates the remainder of the story.<eos>

									_a					:				Tuple				=							model.generate(lowerCamelCase_     ,max_length=200     ,do_sample=lowerCamelCase_		)
									self.assertListEqual(output_ids[0].numpy().tolist()     ,lowerCamelCase_		)









'''simple docstring'''

__lowerCAmelCase						      =       range(2, 20 + 1)
__lowerCAmelCase						      =       [10**k for k in range(ks[-1] + 1)]
__lowerCAmelCase						      =       {}



def 					__lowerCamelCase					(				lowerCAmelCase_						,      lowerCAmelCase_						,      lowerCAmelCase_						,      lowerCAmelCase_  )      ->				Optional[Any]:
		_a					:				Optional[int]				=							sum(a_i[j] for j in range(lowerCAmelCase_						,      len(lowerCAmelCase_  )  )  )
		_a					:				List[str]				=							sum(a_i[j] * base[j] for j in range(min(len(lowerCAmelCase_  )						,      lowerCAmelCase_  )  )  )

		_a	, _a					:				Any				=							0, 0
		_a					:				Any				=							n - i

		_a					:				List[Any]				=							memo.get(lowerCAmelCase_  )

		if sub_memo is not None:
				_a					:				Tuple				=							sub_memo.get(lowerCAmelCase_  )

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

						if max_jump >= 0:
								_a	, _a	, _a					:				Tuple				=							jumps[max_jump]
								# since the difference between jumps is cached, add c
								_a					:				Union[str, Any]				=							diff + c
								for j in range(min(lowerCAmelCase_						,      len(lowerCAmelCase_  )  )  ):
										_a	, _a					:				Dict				=							divmod(lowerCAmelCase_						,      10  )
								if new_c > 0:
										add(lowerCAmelCase_						,      lowerCAmelCase_						,      lowerCAmelCase_  )

				else:
						_a					:				Tuple				=							[]
		else:
				_a					:				Any				=							{c: []}
				_a					:				Optional[Any]				=							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					:				Dict				=							next_term(lowerCAmelCase_						,      k - 1						,      i + dn						,      lowerCAmelCase_  )
						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					:				Any				=							compute(lowerCAmelCase_						,      lowerCAmelCase_						,      i + dn						,      lowerCAmelCase_  )
				diff += _diff
				dn += terms_jumped

		_a					:				Tuple				=							sub_memo[c]

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

		# cache the jump for this value digitsum(b) and c
		sub_memo[c].insert(lowerCAmelCase_						,      (diff, dn, k)  )
		return (diff, dn)



def 					__lowerCamelCase					(				lowerCAmelCase_						,      lowerCAmelCase_						,      lowerCAmelCase_						,      lowerCAmelCase_  )      ->				str:
		if i >= n:
				return 0, i
		if k > len(lowerCAmelCase_  ):
				a_i.extend([0 for _ in range(k - len(lowerCAmelCase_  )  )]  )

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

		while i < n:
				i += 1
				_a					:				Any				=							ds_c + ds_b
				diff += addend
				_a					:				int				=							0
				for j in range(lowerCAmelCase_  ):
						_a					:				Optional[Any]				=							a_i[j] + addend
						_a	, _a					:				Tuple				=							divmod(lowerCAmelCase_						,      10  )

						ds_c += a_i[j]

				if addend > 0:
						break

		if addend > 0:
				add(lowerCAmelCase_						,      lowerCAmelCase_						,      lowerCAmelCase_  )
		return diff, i - start_i



def 					__lowerCamelCase					(				lowerCAmelCase_						,      lowerCAmelCase_						,      lowerCAmelCase_  )      ->				int:
		for j in range(lowerCAmelCase_						,      len(lowerCAmelCase_  )  ):
				_a					:				Optional[Any]				=							digits[j] + addend
				if s >= 10:
						_a	, _a					:				List[str]				=							divmod(lowerCAmelCase_						,      10  )
						_a					:				List[str]				=							addend // 10 + quotient
				else:
						_a					:				Optional[Any]				=							s
						_a					:				Optional[Any]				=							addend // 10

				if addend == 0:
						break

		while addend > 0:
				_a	, _a					:				List[str]				=							divmod(lowerCAmelCase_						,      10  )
				digits.append(lowerCAmelCase_  )



def 					__lowerCamelCase					(				lowerCAmelCase_ = 10**15  )      ->				int:
		_a					:				Dict				=							[1]
		_a					:				int				=							1
		_a					:				Tuple				=							0
		while True:
				_a	, _a					:				str				=							next_term(lowerCAmelCase_						,      20						,      i + dn						,      lowerCAmelCase_  )
				dn += terms_jumped
				if dn == n - i:
						break

		_a					:				Union[str, Any]				=							0
		for j in range(len(lowerCAmelCase_  )  ):
				a_n += digits[j] * 10**j
		return a_n


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




