






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







def 		SCREAMING_SNAKE_CASE							(					__lowerCAmelCase					,    __lowerCAmelCase					,    __lowerCAmelCase					,    __lowerCAmelCase			) ->	str:
     UpperCamelCase__			:   Dict       				=  sum(a_i[j] for j in range(__lowerCAmelCase					,    len(__lowerCAmelCase			)			)			)
     UpperCamelCase__			:   List[str]       				=  sum(a_i[j] * base[j] for j in range(min(len(__lowerCAmelCase			)					,    __lowerCAmelCase			)			)			)

     UpperCamelCase__				,     UpperCamelCase__			:   List[Any]       				=  0, 0
     UpperCamelCase__			:   int       				=  n - i

     UpperCamelCase__			:   Dict       				=  memo.get(__lowerCAmelCase			)

     if sub_memo is not None:
          UpperCamelCase__			:   Optional[int]       				=  sub_memo.get(__lowerCAmelCase			)

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

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

          else:
               UpperCamelCase__			:   List[Any]       				=  []
     else:
          UpperCamelCase__			:   List[str]       				=  {c: []}
          UpperCamelCase__			:   int       				=  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__			:   str       				=  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
          UpperCamelCase__				,     UpperCamelCase__			:   Union[str, Any]       				=  compute(__lowerCAmelCase					,    __lowerCAmelCase					,    i + dn					,    __lowerCAmelCase			)
          diff += _diff
          dn += terms_jumped

     UpperCamelCase__			:   Optional[int]       				=  sub_memo[c]

     # keep jumps sorted by # of terms skipped
     UpperCamelCase__			:   Optional[int]       				=  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 		SCREAMING_SNAKE_CASE							(					__lowerCAmelCase					,    __lowerCAmelCase					,    __lowerCAmelCase					,    __lowerCAmelCase			) ->	Any:
     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)
     UpperCamelCase__			:   str       				=  i
     UpperCamelCase__				,     UpperCamelCase__				,     UpperCamelCase__			:   Union[str, Any]       				=  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
          UpperCamelCase__			:   Optional[int]       				=  ds_c + ds_b
          diff += addend
          UpperCamelCase__			:   Any       				=  0
          for j in range(__lowerCAmelCase			):
               UpperCamelCase__			:   Optional[int]       				=  a_i[j] + addend
               UpperCamelCase__				,     UpperCamelCase__			:   List[Any]       				=  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 		SCREAMING_SNAKE_CASE							(					__lowerCAmelCase					,    __lowerCAmelCase					,    __lowerCAmelCase			) ->	Optional[int]:
     for j in range(__lowerCAmelCase					,    len(__lowerCAmelCase			)			):
          UpperCamelCase__			:   Dict       				=  digits[j] + addend
          if s >= 10:
               UpperCamelCase__				,     UpperCamelCase__			:   Optional[int]       				=  divmod(__lowerCAmelCase					,    10			)
               UpperCamelCase__			:   Dict       				=  addend // 10 + quotient
          else:
               UpperCamelCase__			:   Union[str, Any]       				=  s
               UpperCamelCase__			:   Optional[Any]       				=  addend // 10

          if addend == 0:
               break

     while addend > 0:
          UpperCamelCase__				,     UpperCamelCase__			:   Tuple       				=  divmod(__lowerCAmelCase					,    10			)
          digits.append(__lowerCAmelCase			)







def 		SCREAMING_SNAKE_CASE							(					__lowerCAmelCase = 10**15			) ->	int:
     UpperCamelCase__			:   List[str]       				=  [1]
     UpperCamelCase__			:   List[Any]       				=  1
     UpperCamelCase__			:   Dict       				=  0
     while True:
          UpperCamelCase__				,     UpperCamelCase__			:   Optional[Any]       				=  next_term(__lowerCAmelCase					,    20					,    i + dn					,    __lowerCAmelCase			)
          dn += terms_jumped
          if dn == n - i:
               break

     UpperCamelCase__			:   Dict       				=  0
     for j in range(len(__lowerCAmelCase			)			):
          a_n += digits[j] * 10**j
     return a_n


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







import os
import tempfile
from functools import partial
from unittest import TestCase
from unittest.mock import patch

import datasets
import datasets.config

from .utils import require_beam





class 			__a  (    datasets.BeamBasedBuilder       ):







 def 					__lowercase					(		self					:   List[str]						):


      '''simple docstring'''






      return datasets.DatasetInfo(
          features=datasets.Features({"content": datasets.Value("string"						)}						)							,   supervised_keys=SCREAMING_SNAKE_CASE							,   )







 def 					__lowercase					(		self					:   List[Any]							,   SCREAMING_SNAKE_CASE					:   Optional[int]							,   SCREAMING_SNAKE_CASE					:   Any						):


      '''simple docstring'''






      return [datasets.SplitGenerator(name=datasets.Split.TRAIN							,   gen_kwargs={"examples": get_test_dummy_examples()}						)]







 def 					__lowercase					(		self					:   List[Any]							,   SCREAMING_SNAKE_CASE					:   Tuple							,   SCREAMING_SNAKE_CASE					:   int						):


      '''simple docstring'''






      import apache_beam as beam

      return pipeline | "Load Examples" >> beam.Create(SCREAMING_SNAKE_CASE						)







class 			__a  (    datasets.BeamBasedBuilder       ):







 def 					__lowercase					(		self					:   Any						):


      '''simple docstring'''






      return datasets.DatasetInfo(
          features=datasets.Features({"a": datasets.Sequence({"b": datasets.Value("string"						)}						)}						)							,   supervised_keys=SCREAMING_SNAKE_CASE							,   )







 def 					__lowercase					(		self					:   Any							,   SCREAMING_SNAKE_CASE					:   Tuple							,   SCREAMING_SNAKE_CASE					:   List[Any]						):


      '''simple docstring'''






      return [
          datasets.SplitGenerator(name=datasets.Split.TRAIN							,   gen_kwargs={"examples": get_test_nested_examples()}						)
      ]







 def 					__lowercase					(		self					:   List[Any]							,   SCREAMING_SNAKE_CASE					:   Tuple							,   SCREAMING_SNAKE_CASE					:   Any						):


      '''simple docstring'''






      import apache_beam as beam

      return pipeline | "Load Examples" >> beam.Create(SCREAMING_SNAKE_CASE						)







def 		SCREAMING_SNAKE_CASE							(					) ->	List[str]:
     return [(i, {"content": content}) for i, content in enumerate(["foo", "bar", "foobar"]			)]







def 		SCREAMING_SNAKE_CASE							(					) ->	Optional[Any]:
     return [(i, {"a": {"b": [content]}}) for i, content in enumerate(["foo", "bar", "foobar"]			)]





class 			__a  (    A__       ):







 @require_beam
 def 					__lowercase					(		self					:   Optional[int]						):


      '''simple docstring'''






      UpperCamelCase__			:   int       				=  len(get_test_dummy_examples()						)
      with tempfile.TemporaryDirectory() as tmp_cache_dir:
           UpperCamelCase__			:   List[Any]       				=  DummyBeamDataset(cache_dir=SCREAMING_SNAKE_CASE							,   beam_runner="DirectRunner"						)
           builder.download_and_prepare()
           self.assertTrue(
               os.path.exists(
                   os.path.join(SCREAMING_SNAKE_CASE							,   builder.name							,   "default"							,   "0.0.0"							,   F'{builder.name}-train.arrow'						)						)						)
           self.assertDictEqual(builder.info.features							,   datasets.Features({"content": datasets.Value("string"						)}						)						)
           UpperCamelCase__			:   Optional[Any]       				=  builder.as_dataset()
           self.assertEqual(dset["train"].num_rows							,   SCREAMING_SNAKE_CASE						)
           self.assertEqual(dset["train"].info.splits["train"].num_examples							,   SCREAMING_SNAKE_CASE						)
           self.assertDictEqual(dset["train"][0]							,   get_test_dummy_examples()[0][1]						)
           self.assertDictEqual(
               dset["train"][expected_num_examples - 1]							,   get_test_dummy_examples()[expected_num_examples - 1][1]						)
           self.assertTrue(
               os.path.exists(os.path.join(SCREAMING_SNAKE_CASE							,   builder.name							,   "default"							,   "0.0.0"							,   "dataset_info.json"						)						)						)
           del dset







 @require_beam
 def 					__lowercase					(		self					:   Any						):


      '''simple docstring'''






      import apache_beam as beam

      UpperCamelCase__			:   Any       				=  beam.io.parquetio.WriteToParquet

      UpperCamelCase__			:   Tuple       				=  len(get_test_dummy_examples()						)
      with tempfile.TemporaryDirectory() as tmp_cache_dir:
           UpperCamelCase__			:   str       				=  DummyBeamDataset(cache_dir=SCREAMING_SNAKE_CASE							,   beam_runner="DirectRunner"						)
           with patch("apache_beam.io.parquetio.WriteToParquet"						) as write_parquet_mock:
                UpperCamelCase__			:   Optional[Any]       				=  partial(SCREAMING_SNAKE_CASE							,   num_shards=2						)
                builder.download_and_prepare()
           self.assertTrue(
               os.path.exists(
                   os.path.join(
                       SCREAMING_SNAKE_CASE							,   builder.name							,   "default"							,   "0.0.0"							,   F'{builder.name}-train-00000-of-00002.arrow'						)						)						)
           self.assertTrue(
               os.path.exists(
                   os.path.join(
                       SCREAMING_SNAKE_CASE							,   builder.name							,   "default"							,   "0.0.0"							,   F'{builder.name}-train-00000-of-00002.arrow'						)						)						)
           self.assertDictEqual(builder.info.features							,   datasets.Features({"content": datasets.Value("string"						)}						)						)
           UpperCamelCase__			:   List[Any]       				=  builder.as_dataset()
           self.assertEqual(dset["train"].num_rows							,   SCREAMING_SNAKE_CASE						)
           self.assertEqual(dset["train"].info.splits["train"].num_examples							,   SCREAMING_SNAKE_CASE						)
           # Order is not preserved when sharding, so we just check that all the elements are there
           self.assertListEqual(sorted(dset["train"]["content"]						)							,   sorted(["foo", "bar", "foobar"]						)						)
           self.assertTrue(
               os.path.exists(os.path.join(SCREAMING_SNAKE_CASE							,   builder.name							,   "default"							,   "0.0.0"							,   "dataset_info.json"						)						)						)
           del dset







 @require_beam
 def 					__lowercase					(		self					:   List[Any]						):


      '''simple docstring'''






      with tempfile.TemporaryDirectory() as tmp_cache_dir:
           UpperCamelCase__			:   int       				=  DummyBeamDataset(cache_dir=SCREAMING_SNAKE_CASE						)
           self.assertRaises(datasets.builder.MissingBeamOptions							,   builder.download_and_prepare						)







 @require_beam
 def 					__lowercase					(		self					:   List[Any]						):


      '''simple docstring'''






      UpperCamelCase__			:   List[Any]       				=  len(get_test_nested_examples()						)
      with tempfile.TemporaryDirectory() as tmp_cache_dir:
           UpperCamelCase__			:   Any       				=  NestedBeamDataset(cache_dir=SCREAMING_SNAKE_CASE							,   beam_runner="DirectRunner"						)
           builder.download_and_prepare()
           self.assertTrue(
               os.path.exists(
                   os.path.join(SCREAMING_SNAKE_CASE							,   builder.name							,   "default"							,   "0.0.0"							,   F'{builder.name}-train.arrow'						)						)						)
           self.assertDictEqual(
               builder.info.features							,   datasets.Features({"a": datasets.Sequence({"b": datasets.Value("string"						)}						)}						)						)
           UpperCamelCase__			:   List[Any]       				=  builder.as_dataset()
           self.assertEqual(dset["train"].num_rows							,   SCREAMING_SNAKE_CASE						)
           self.assertEqual(dset["train"].info.splits["train"].num_examples							,   SCREAMING_SNAKE_CASE						)
           self.assertDictEqual(dset["train"][0]							,   get_test_nested_examples()[0][1]						)
           self.assertDictEqual(
               dset["train"][expected_num_examples - 1]							,   get_test_nested_examples()[expected_num_examples - 1][1]						)
           self.assertTrue(
               os.path.exists(os.path.join(SCREAMING_SNAKE_CASE							,   builder.name							,   "default"							,   "0.0.0"							,   "dataset_info.json"						)						)						)
           del dset