



"""simple docstring"""




_lowerCAmelCase							:   Tuple				=				range(2, 20 + 1)
_lowerCAmelCase							:   List[str]				=				[10**k for k in range(ks[-1] + 1)]
_lowerCAmelCase							:   dict[int, dict[int, list[list[int]]]]				=				{}

def 		__snake_case		( SCREAMING_SNAKE_CASE__      :		int		,    SCREAMING_SNAKE_CASE__      :		Union[str, Any]		,    SCREAMING_SNAKE_CASE__      :		Tuple		,    SCREAMING_SNAKE_CASE__      :		int							)    ->  Optional[Any]:





     '''simple docstring'''

     _UpperCAmelCase     :      Dict														=       sum(a_i[j] for j in range(SCREAMING_SNAKE_CASE__		,    len(SCREAMING_SNAKE_CASE__							)							)							)
     _UpperCAmelCase     :      Any														=       sum(a_i[j] * base[j] for j in range(min(len(SCREAMING_SNAKE_CASE__							)		,    SCREAMING_SNAKE_CASE__							)							)							)

     _UpperCAmelCase							,			_UpperCAmelCase     :      Tuple														=       0, 0
     _UpperCAmelCase     :      Dict														=       n - i

     _UpperCAmelCase     :      List[str]														=       memo.get(SCREAMING_SNAKE_CASE__							)

     if sub_memo is not None:
          _UpperCAmelCase     :      Union[str, Any]														=       sub_memo.get(SCREAMING_SNAKE_CASE__							)

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

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

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

     _UpperCAmelCase     :      Dict														=       sub_memo[c]

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

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

def 		__snake_case		( SCREAMING_SNAKE_CASE__      :		Optional[int]		,    SCREAMING_SNAKE_CASE__      :		Tuple		,    SCREAMING_SNAKE_CASE__      :		List[Any]		,    SCREAMING_SNAKE_CASE__      :		str							)    ->  Optional[int]:





     '''simple docstring'''

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

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

     while i < n:
          i += 1
          _UpperCAmelCase     :      str														=       ds_c + ds_b
          diff += addend
          _UpperCAmelCase     :      Tuple														=       0
          for j in range(SCREAMING_SNAKE_CASE__							):
               _UpperCAmelCase     :      List[Any]														=       a_i[j] + addend
               _UpperCAmelCase							,			_UpperCAmelCase     :      Tuple														=       divmod(SCREAMING_SNAKE_CASE__		,    10							)

               ds_c += a_i[j]

          if addend > 0:
               break

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

def 		__snake_case		( SCREAMING_SNAKE_CASE__      :		Tuple		,    SCREAMING_SNAKE_CASE__      :		List[str]		,    SCREAMING_SNAKE_CASE__      :		List[str]							)    ->  Optional[Any]:





     '''simple docstring'''

     for j in range(SCREAMING_SNAKE_CASE__		,    len(SCREAMING_SNAKE_CASE__							)							):
          _UpperCAmelCase     :      Tuple														=       digits[j] + addend
          if s >= 10:
               _UpperCAmelCase							,			_UpperCAmelCase     :      Optional[int]														=       divmod(SCREAMING_SNAKE_CASE__		,    10							)
               _UpperCAmelCase     :      List[Any]														=       addend // 10 + quotient
          else:
               _UpperCAmelCase     :      Union[str, Any]														=       s
               _UpperCAmelCase     :      Dict														=       addend // 10

          if addend == 0:
               break

     while addend > 0:
          _UpperCAmelCase							,			_UpperCAmelCase     :      Dict														=       divmod(SCREAMING_SNAKE_CASE__		,    10							)
          digits.append(SCREAMING_SNAKE_CASE__							)

def 		__snake_case		( SCREAMING_SNAKE_CASE__      :		int = 10**15							)    ->  int:





     '''simple docstring'''

     _UpperCAmelCase     :      List[Any]														=       [1]
     _UpperCAmelCase     :      Dict														=       1
     _UpperCAmelCase     :      Union[str, Any]														=       0
     while True:
          _UpperCAmelCase							,			_UpperCAmelCase     :      Tuple														=       next_term(SCREAMING_SNAKE_CASE__		,    20		,    i + dn		,    SCREAMING_SNAKE_CASE__							)
          dn += terms_jumped
          if dn == n - i:
               break

     _UpperCAmelCase     :      Tuple														=       0
     for j in range(len(SCREAMING_SNAKE_CASE__							)							):
          a_n += digits[j] * 10**j
     return a_n


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





"""simple docstring"""




import os
import tempfile
import unittest

import numpy as np

from diffusers.utils import is_flax_available
from diffusers.utils.testing_utils import require_flax, slow


if is_flax_available():
 import jax
 import jax.numpy as jnp
 from flax.jax_utils import replicate
 from flax.training.common_utils import shard

 from diffusers import FlaxDDIMScheduler, FlaxDiffusionPipeline, FlaxStableDiffusionPipeline






@require_flax
class       UpperCAmelCase_    (							unittest.TestCase		):



      def 		snake_case_   (	self	:      Optional[int]		):
           with tempfile.TemporaryDirectory() as tmpdirname:
                # pipeline has Flax weights
                _UpperCAmelCase     :      Union[str, Any]														=       FlaxDiffusionPipeline.from_pretrained(
                    "hf-internal-testing/tiny-stable-diffusion-pipe"	,      safety_checker=A	,      cache_dir=A		)

                _UpperCAmelCase     :      List[str]														=       [t[-1] for t in os.walk(os.path.join(A	,      os.listdir(A		)[0]	,      "snapshots"		)		)]
                _UpperCAmelCase     :      Union[str, Any]														=       [item for sublist in all_root_files for item in sublist]

                # None of the downloaded files should be a PyTorch file even if we have some here:
                # https://huggingface.co/hf-internal-testing/tiny-stable-diffusion-pipe/blob/main/unet/diffusion_pytorch_model.bin
                assert not any(f.endswith(".bin"		) for f in files		)







@slow
@require_flax
class       UpperCAmelCase_    (							unittest.TestCase		):



      def 		snake_case_   (	self	:      List[str]		):
           _UpperCAmelCase							,			_UpperCAmelCase     :      int														=       FlaxStableDiffusionPipeline.from_pretrained(
               "hf-internal-testing/tiny-stable-diffusion-pipe"	,      safety_checker=A		)

           _UpperCAmelCase     :      str														=       (
               "A cinematic film still of Morgan Freeman starring as Jimi Hendrix, portrait, 40mm lens, shallow depth of"
               " field, close up, split lighting, cinematic"
           )

           _UpperCAmelCase     :      int														=       jax.random.PRNGKey(0		)
           _UpperCAmelCase     :      List[str]														=       4

           _UpperCAmelCase     :      Any														=       jax.device_count()
           _UpperCAmelCase     :      Tuple														=       num_samples * [prompt]
           _UpperCAmelCase     :      Optional[int]														=       pipeline.prepare_inputs(A		)

           # shard inputs and rng
           _UpperCAmelCase     :      Union[str, Any]														=       replicate(A		)
           _UpperCAmelCase     :      List[Any]														=       jax.random.split(A	,      A		)
           _UpperCAmelCase     :      List[Any]														=       shard(A		)

           _UpperCAmelCase     :      Tuple														=       pipeline(A	,      A	,      A	,      A	,      jit=A		).images

           assert images.shape == (num_samples, 1, 6_4, 6_4, 3)
           if jax.device_count() == 8:
                assert np.abs(np.abs(images[0, 0, :2, :2, -2:]	,      dtype=np.floataa		).sum() - 4.1_514_745		) < 1e-3
                assert np.abs(np.abs(A	,      dtype=np.floataa		).sum() - 49_947.875		) < 5e-1

           _UpperCAmelCase     :      Optional[int]														=       pipeline.numpy_to_pil(np.asarray(images.reshape((num_samples,) + images.shape[-3:]		)		)		)
           assert len(A		) == num_samples



      def 		snake_case_   (	self	:      Union[str, Any]		):
           _UpperCAmelCase							,			_UpperCAmelCase     :      Optional[Any]														=       FlaxStableDiffusionPipeline.from_pretrained(
               "CompVis/stable-diffusion-v1-4"	,      revision="flax"	,      safety_checker=A		)

           _UpperCAmelCase     :      Dict														=       (
               "A cinematic film still of Morgan Freeman starring as Jimi Hendrix, portrait, 40mm lens, shallow depth of"
               " field, close up, split lighting, cinematic"
           )

           _UpperCAmelCase     :      Dict														=       jax.random.PRNGKey(0		)
           _UpperCAmelCase     :      str														=       5_0

           _UpperCAmelCase     :      List[str]														=       jax.device_count()
           _UpperCAmelCase     :      Any														=       num_samples * [prompt]
           _UpperCAmelCase     :      Dict														=       pipeline.prepare_inputs(A		)

           # shard inputs and rng
           _UpperCAmelCase     :      Dict														=       replicate(A		)
           _UpperCAmelCase     :      str														=       jax.random.split(A	,      A		)
           _UpperCAmelCase     :      Optional[Any]														=       shard(A		)

           _UpperCAmelCase     :      List[Any]														=       pipeline(A	,      A	,      A	,      A	,      jit=A		).images

           assert images.shape == (num_samples, 1, 5_1_2, 5_1_2, 3)
           if jax.device_count() == 8:
                assert np.abs((np.abs(images[0, 0, :2, :2, -2:]	,      dtype=np.floataa		).sum() - 0.05_652_401)		) < 1e-3
                assert np.abs((np.abs(A	,      dtype=np.floataa		).sum() - 2_383_808.2)		) < 5e-1



      def 		snake_case_   (	self	:      List[Any]		):
           _UpperCAmelCase							,			_UpperCAmelCase     :      List[Any]														=       FlaxStableDiffusionPipeline.from_pretrained(
               "CompVis/stable-diffusion-v1-4"	,      revision="bf16"	,      dtype=jnp.bfloataa	,      safety_checker=A		)

           _UpperCAmelCase     :      Any														=       (
               "A cinematic film still of Morgan Freeman starring as Jimi Hendrix, portrait, 40mm lens, shallow depth of"
               " field, close up, split lighting, cinematic"
           )

           _UpperCAmelCase     :      List[Any]														=       jax.random.PRNGKey(0		)
           _UpperCAmelCase     :      List[Any]														=       5_0

           _UpperCAmelCase     :      Union[str, Any]														=       jax.device_count()
           _UpperCAmelCase     :      Optional[int]														=       num_samples * [prompt]
           _UpperCAmelCase     :      Union[str, Any]														=       pipeline.prepare_inputs(A		)

           # shard inputs and rng
           _UpperCAmelCase     :      int														=       replicate(A		)
           _UpperCAmelCase     :      Optional[int]														=       jax.random.split(A	,      A		)
           _UpperCAmelCase     :      str														=       shard(A		)

           _UpperCAmelCase     :      Union[str, Any]														=       pipeline(A	,      A	,      A	,      A	,      jit=A		).images

           assert images.shape == (num_samples, 1, 5_1_2, 5_1_2, 3)
           if jax.device_count() == 8:
                assert np.abs((np.abs(images[0, 0, :2, :2, -2:]	,      dtype=np.floataa		).sum() - 0.04_003_906)		) < 1e-3
                assert np.abs((np.abs(A	,      dtype=np.floataa		).sum() - 2_373_516.75)		) < 5e-1



      def 		snake_case_   (	self	:      int		):
           _UpperCAmelCase							,			_UpperCAmelCase     :      Dict														=       FlaxStableDiffusionPipeline.from_pretrained(
               "CompVis/stable-diffusion-v1-4"	,      revision="bf16"	,      dtype=jnp.bfloataa		)

           _UpperCAmelCase     :      str														=       (
               "A cinematic film still of Morgan Freeman starring as Jimi Hendrix, portrait, 40mm lens, shallow depth of"
               " field, close up, split lighting, cinematic"
           )

           _UpperCAmelCase     :      Optional[int]														=       jax.random.PRNGKey(0		)
           _UpperCAmelCase     :      Dict														=       5_0

           _UpperCAmelCase     :      Union[str, Any]														=       jax.device_count()
           _UpperCAmelCase     :      str														=       num_samples * [prompt]
           _UpperCAmelCase     :      int														=       pipeline.prepare_inputs(A		)

           # shard inputs and rng
           _UpperCAmelCase     :      Optional[int]														=       replicate(A		)
           _UpperCAmelCase     :      Tuple														=       jax.random.split(A	,      A		)
           _UpperCAmelCase     :      Dict														=       shard(A		)

           _UpperCAmelCase     :      Optional[Any]														=       pipeline(A	,      A	,      A	,      A	,      jit=A		).images

           assert images.shape == (num_samples, 1, 5_1_2, 5_1_2, 3)
           if jax.device_count() == 8:
                assert np.abs((np.abs(images[0, 0, :2, :2, -2:]	,      dtype=np.floataa		).sum() - 0.04_003_906)		) < 1e-3
                assert np.abs((np.abs(A	,      dtype=np.floataa		).sum() - 2_373_516.75)		) < 5e-1



      def 		snake_case_   (	self	:      Optional[Any]		):
           _UpperCAmelCase     :      Dict														=       FlaxDDIMScheduler(
               beta_start=0.00_085	,      beta_end=0.012	,      beta_schedule="scaled_linear"	,      set_alpha_to_one=A	,      steps_offset=1	,      )

           _UpperCAmelCase							,			_UpperCAmelCase     :      Dict														=       FlaxStableDiffusionPipeline.from_pretrained(
               "CompVis/stable-diffusion-v1-4"	,      revision="bf16"	,      dtype=jnp.bfloataa	,      scheduler=A	,      safety_checker=A	,      )
           _UpperCAmelCase     :      Union[str, Any]														=       scheduler.create_state()

           _UpperCAmelCase     :      str														=       scheduler_state

           _UpperCAmelCase     :      Union[str, Any]														=       (
               "A cinematic film still of Morgan Freeman starring as Jimi Hendrix, portrait, 40mm lens, shallow depth of"
               " field, close up, split lighting, cinematic"
           )

           _UpperCAmelCase     :      str														=       jax.random.PRNGKey(0		)
           _UpperCAmelCase     :      List[str]														=       5_0

           _UpperCAmelCase     :      Optional[int]														=       jax.device_count()
           _UpperCAmelCase     :      int														=       num_samples * [prompt]
           _UpperCAmelCase     :      Optional[int]														=       pipeline.prepare_inputs(A		)

           # shard inputs and rng
           _UpperCAmelCase     :      List[Any]														=       replicate(A		)
           _UpperCAmelCase     :      Tuple														=       jax.random.split(A	,      A		)
           _UpperCAmelCase     :      Union[str, Any]														=       shard(A		)

           _UpperCAmelCase     :      Dict														=       pipeline(A	,      A	,      A	,      A	,      jit=A		).images

           assert images.shape == (num_samples, 1, 5_1_2, 5_1_2, 3)
           if jax.device_count() == 8:
                assert np.abs((np.abs(images[0, 0, :2, :2, -2:]	,      dtype=np.floataa		).sum() - 0.045_043_945)		) < 1e-3
                assert np.abs((np.abs(A	,      dtype=np.floataa		).sum() - 2_347_693.5)		) < 5e-1



      def 		snake_case_   (	self	:      int		):
           _UpperCAmelCase     :      Optional[Any]														=       (
               "A cinematic film still of Morgan Freeman starring as Jimi Hendrix, portrait, 40mm lens, shallow depth of"
               " field, close up, split lighting, cinematic"
           )

           _UpperCAmelCase     :      Optional[Any]														=       jax.device_count()
           _UpperCAmelCase     :      Union[str, Any]														=       num_samples * [prompt]
           _UpperCAmelCase     :      Optional[Any]														=       jax.random.split(jax.random.PRNGKey(0		)	,      A		)

           _UpperCAmelCase							,			_UpperCAmelCase     :      str														=       FlaxStableDiffusionPipeline.from_pretrained(
               "CompVis/stable-diffusion-v1-4"	,      revision="bf16"	,      dtype=jnp.bfloataa	,      safety_checker=A	,      )

           _UpperCAmelCase     :      int														=       replicate(A		)
           _UpperCAmelCase     :      Union[str, Any]														=       pipeline.prepare_inputs(A		)
           _UpperCAmelCase     :      int														=       shard(A		)
           _UpperCAmelCase     :      Dict														=       pipeline(A	,      A	,      A	,      jit=A		).images
           assert images.shape == (num_samples, 1, 5_1_2, 5_1_2, 3)
           _UpperCAmelCase     :      List[str]														=       images[2, 0, 2_5_6, 1_0:1_7, 1]

           # With memory efficient attention
           _UpperCAmelCase							,			_UpperCAmelCase     :      str														=       FlaxStableDiffusionPipeline.from_pretrained(
               "CompVis/stable-diffusion-v1-4"	,      revision="bf16"	,      dtype=jnp.bfloataa	,      safety_checker=A	,      use_memory_efficient_attention=A	,      )

           _UpperCAmelCase     :      Any														=       replicate(A		)
           _UpperCAmelCase     :      str														=       pipeline.prepare_inputs(A		)
           _UpperCAmelCase     :      Tuple														=       shard(A		)
           _UpperCAmelCase     :      Tuple														=       pipeline(A	,      A	,      A	,      jit=A		).images
           assert images_eff.shape == (num_samples, 1, 5_1_2, 5_1_2, 3)
           _UpperCAmelCase     :      str														=       images[2, 0, 2_5_6, 1_0:1_7, 1]

           # I checked the results visually and they are very similar. However, I saw that the max diff is `1` and the `sum`
           # over the 8 images is exactly `256`, which is very suspicious. Testing a random slice for now.
           assert abs(slice_eff - slice		).max() < 1e-2
