

'''simple docstring'''







import unittest

import numpy as np

from transformers.testing_utils import require_flax, require_tf, require_torch
from transformers.utils import (
    expand_dims,
    flatten_dict,
    is_flax_available,
    is_tf_available,
    is_torch_available,
    reshape,
    squeeze,
    transpose,
)


if is_flax_available():
      import jax.numpy as jnp

if is_tf_available():
      import tensorflow as tf

if is_torch_available():
      import torch


class 					A__      (      unittest.TestCase			):



    def 					snake_case_			(					self       )						->      Tuple:





           '''simple docstring'''
           A_						=      {
               """task_specific_params""": {
                   """summarization""": {"""length_penalty""": 1.0, """max_length""": 128, """min_length""": 12, """num_beams""": 4},
                   """summarization_cnn""": {"""length_penalty""": 2.0, """max_length""": 142, """min_length""": 56, """num_beams""": 4},
                   """summarization_xsum""": {"""length_penalty""": 1.0, """max_length""": 62, """min_length""": 11, """num_beams""": 6},
               }
           }
           A_						=      {
               """task_specific_params.summarization.length_penalty""": 1.0,
               """task_specific_params.summarization.max_length""": 128,
               """task_specific_params.summarization.min_length""": 12,
               """task_specific_params.summarization.num_beams""": 4,
               """task_specific_params.summarization_cnn.length_penalty""": 2.0,
               """task_specific_params.summarization_cnn.max_length""": 142,
               """task_specific_params.summarization_cnn.min_length""": 56,
               """task_specific_params.summarization_cnn.num_beams""": 4,
               """task_specific_params.summarization_xsum.length_penalty""": 1.0,
               """task_specific_params.summarization_xsum.max_length""": 62,
               """task_specific_params.summarization_xsum.min_length""": 11,
               """task_specific_params.summarization_xsum.num_beams""": 6,
           }

           self.assertEqual(flatten_dict(UpperCamelCase__       )		,				UpperCamelCase__       )



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





           '''simple docstring'''
           A_						=      np.random.randn(3		,				4       )
           self.assertTrue(np.allclose(transpose(UpperCamelCase__       )		,				x.transpose()       )       )

           A_						=      np.random.randn(3		,				4		,				5       )
           self.assertTrue(np.allclose(transpose(UpperCamelCase__		,				axes=(1, 2, 0)       )		,				x.transpose((1, 2, 0)       )       )       )



    @require_torch
    def 					snake_case_			(					self       )						->      Optional[Any]:





           '''simple docstring'''
           A_						=      np.random.randn(3		,				4       )
           A_						=      torch.tensor(UpperCamelCase__       )
           self.assertTrue(np.allclose(transpose(UpperCamelCase__       )		,				transpose(UpperCamelCase__       ).numpy()       )       )

           A_						=      np.random.randn(3		,				4		,				5       )
           A_						=      torch.tensor(UpperCamelCase__       )
           self.assertTrue(np.allclose(transpose(UpperCamelCase__		,				axes=(1, 2, 0)       )		,				transpose(UpperCamelCase__		,				axes=(1, 2, 0)       ).numpy()       )       )



    @require_tf
    def 					snake_case_			(					self       )						->      str:





           '''simple docstring'''
           A_						=      np.random.randn(3		,				4       )
           A_						=      tf.constant(UpperCamelCase__       )
           self.assertTrue(np.allclose(transpose(UpperCamelCase__       )		,				transpose(UpperCamelCase__       ).numpy()       )       )

           A_						=      np.random.randn(3		,				4		,				5       )
           A_						=      tf.constant(UpperCamelCase__       )
           self.assertTrue(np.allclose(transpose(UpperCamelCase__		,				axes=(1, 2, 0)       )		,				transpose(UpperCamelCase__		,				axes=(1, 2, 0)       ).numpy()       )       )



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





           '''simple docstring'''
           A_						=      np.random.randn(3		,				4       )
           A_						=      jnp.array(UpperCamelCase__       )
           self.assertTrue(np.allclose(transpose(UpperCamelCase__       )		,				np.asarray(transpose(UpperCamelCase__       )       )       )       )

           A_						=      np.random.randn(3		,				4		,				5       )
           A_						=      jnp.array(UpperCamelCase__       )
           self.assertTrue(np.allclose(transpose(UpperCamelCase__		,				axes=(1, 2, 0)       )		,				np.asarray(transpose(UpperCamelCase__		,				axes=(1, 2, 0)       )       )       )       )



    def 					snake_case_			(					self       )						->      Dict:





           '''simple docstring'''
           A_						=      np.random.randn(3		,				4       )
           self.assertTrue(np.allclose(reshape(UpperCamelCase__		,				(4, 3)       )		,				np.reshape(UpperCamelCase__		,				(4, 3)       )       )       )

           A_						=      np.random.randn(3		,				4		,				5       )
           self.assertTrue(np.allclose(reshape(UpperCamelCase__		,				(12, 5)       )		,				np.reshape(UpperCamelCase__		,				(12, 5)       )       )       )



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





           '''simple docstring'''
           A_						=      np.random.randn(3		,				4       )
           A_						=      torch.tensor(UpperCamelCase__       )
           self.assertTrue(np.allclose(reshape(UpperCamelCase__		,				(4, 3)       )		,				reshape(UpperCamelCase__		,				(4, 3)       ).numpy()       )       )

           A_						=      np.random.randn(3		,				4		,				5       )
           A_						=      torch.tensor(UpperCamelCase__       )
           self.assertTrue(np.allclose(reshape(UpperCamelCase__		,				(12, 5)       )		,				reshape(UpperCamelCase__		,				(12, 5)       ).numpy()       )       )



    @require_tf
    def 					snake_case_			(					self       )						->      str:





           '''simple docstring'''
           A_						=      np.random.randn(3		,				4       )
           A_						=      tf.constant(UpperCamelCase__       )
           self.assertTrue(np.allclose(reshape(UpperCamelCase__		,				(4, 3)       )		,				reshape(UpperCamelCase__		,				(4, 3)       ).numpy()       )       )

           A_						=      np.random.randn(3		,				4		,				5       )
           A_						=      tf.constant(UpperCamelCase__       )
           self.assertTrue(np.allclose(reshape(UpperCamelCase__		,				(12, 5)       )		,				reshape(UpperCamelCase__		,				(12, 5)       ).numpy()       )       )



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





           '''simple docstring'''
           A_						=      np.random.randn(3		,				4       )
           A_						=      jnp.array(UpperCamelCase__       )
           self.assertTrue(np.allclose(reshape(UpperCamelCase__		,				(4, 3)       )		,				np.asarray(reshape(UpperCamelCase__		,				(4, 3)       )       )       )       )

           A_						=      np.random.randn(3		,				4		,				5       )
           A_						=      jnp.array(UpperCamelCase__       )
           self.assertTrue(np.allclose(reshape(UpperCamelCase__		,				(12, 5)       )		,				np.asarray(reshape(UpperCamelCase__		,				(12, 5)       )       )       )       )



    def 					snake_case_			(					self       )						->      str:





           '''simple docstring'''
           A_						=      np.random.randn(1		,				3		,				4       )
           self.assertTrue(np.allclose(squeeze(UpperCamelCase__       )		,				np.squeeze(UpperCamelCase__       )       )       )

           A_						=      np.random.randn(1		,				4		,				1		,				5       )
           self.assertTrue(np.allclose(squeeze(UpperCamelCase__		,				axis=2       )		,				np.squeeze(UpperCamelCase__		,				axis=2       )       )       )



    @require_torch
    def 					snake_case_			(					self       )						->      List[Any]:





           '''simple docstring'''
           A_						=      np.random.randn(1		,				3		,				4       )
           A_						=      torch.tensor(UpperCamelCase__       )
           self.assertTrue(np.allclose(squeeze(UpperCamelCase__       )		,				squeeze(UpperCamelCase__       ).numpy()       )       )

           A_						=      np.random.randn(1		,				4		,				1		,				5       )
           A_						=      torch.tensor(UpperCamelCase__       )
           self.assertTrue(np.allclose(squeeze(UpperCamelCase__		,				axis=2       )		,				squeeze(UpperCamelCase__		,				axis=2       ).numpy()       )       )



    @require_tf
    def 					snake_case_			(					self       )						->      Any:





           '''simple docstring'''
           A_						=      np.random.randn(1		,				3		,				4       )
           A_						=      tf.constant(UpperCamelCase__       )
           self.assertTrue(np.allclose(squeeze(UpperCamelCase__       )		,				squeeze(UpperCamelCase__       ).numpy()       )       )

           A_						=      np.random.randn(1		,				4		,				1		,				5       )
           A_						=      tf.constant(UpperCamelCase__       )
           self.assertTrue(np.allclose(squeeze(UpperCamelCase__		,				axis=2       )		,				squeeze(UpperCamelCase__		,				axis=2       ).numpy()       )       )



    @require_flax
    def 					snake_case_			(					self       )						->      int:





           '''simple docstring'''
           A_						=      np.random.randn(1		,				3		,				4       )
           A_						=      jnp.array(UpperCamelCase__       )
           self.assertTrue(np.allclose(squeeze(UpperCamelCase__       )		,				np.asarray(squeeze(UpperCamelCase__       )       )       )       )

           A_						=      np.random.randn(1		,				4		,				1		,				5       )
           A_						=      jnp.array(UpperCamelCase__       )
           self.assertTrue(np.allclose(squeeze(UpperCamelCase__		,				axis=2       )		,				np.asarray(squeeze(UpperCamelCase__		,				axis=2       )       )       )       )



    def 					snake_case_			(					self       )						->      Any:





           '''simple docstring'''
           A_						=      np.random.randn(3		,				4       )
           self.assertTrue(np.allclose(expand_dims(UpperCamelCase__		,				axis=1       )		,				np.expand_dims(UpperCamelCase__		,				axis=1       )       )       )



    @require_torch
    def 					snake_case_			(					self       )						->      Tuple:





           '''simple docstring'''
           A_						=      np.random.randn(3		,				4       )
           A_						=      torch.tensor(UpperCamelCase__       )
           self.assertTrue(np.allclose(expand_dims(UpperCamelCase__		,				axis=1       )		,				expand_dims(UpperCamelCase__		,				axis=1       ).numpy()       )       )



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





           '''simple docstring'''
           A_						=      np.random.randn(3		,				4       )
           A_						=      tf.constant(UpperCamelCase__       )
           self.assertTrue(np.allclose(expand_dims(UpperCamelCase__		,				axis=1       )		,				expand_dims(UpperCamelCase__		,				axis=1       ).numpy()       )       )







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





           '''simple docstring'''
           A_						=      np.random.randn(3		,				4       )
           A_						=      jnp.array(UpperCamelCase__       )
           self.assertTrue(np.allclose(expand_dims(UpperCamelCase__		,				axis=1       )		,				np.asarray(expand_dims(UpperCamelCase__		,				axis=1       )       )       )       )



'''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() = }""")
