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


def    A (      lowercase					, lowercase					, lowercase					, lowercase				)     ->						Optional[int]:
		'''simple docstring'''

		UpperCamelCase						=  sum(a_i[j] for j in range(lowercase					, len(lowercase				)				)				)
		UpperCamelCase						=  sum(a_i[j] * base[j] for j in range(min(len(lowercase				)					, lowercase				)				)				)

		UpperCamelCase			,						UpperCamelCase						=  0, 0
		UpperCamelCase						=  n - i

		UpperCamelCase						=  memo.get(lowercase				)

		if sub_memo is not None:
				UpperCamelCase						=  sub_memo.get(lowercase				)

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

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

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

		UpperCamelCase						=  sub_memo[c]

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

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


def    A (      lowercase					, lowercase					, lowercase					, lowercase				)     ->						Optional[int]:
		'''simple docstring'''

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

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

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

						ds_c += a_i[j]

				if addend > 0:
						break

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


def    A (      lowercase					, lowercase					, lowercase				)     ->						str:
		'''simple docstring'''

		for j in range(lowercase					, len(lowercase				)				):
				UpperCamelCase						=  digits[j] + addend
				if s >= 10:
						UpperCamelCase			,						UpperCamelCase						=  divmod(lowercase					, 10				)
						UpperCamelCase						=  addend // 10 + quotient
				else:
						UpperCamelCase						=  s
						UpperCamelCase						=  addend // 10

				if addend == 0:
						break

		while addend > 0:
				UpperCamelCase			,						UpperCamelCase						=  divmod(lowercase					, 10				)
				digits.append(lowercase				)


def    A (      lowercase = 10**15				)     ->						int:
		'''simple docstring'''

		UpperCamelCase						=  [1]
		UpperCamelCase						=  1
		UpperCamelCase						=  0
		while True:
				UpperCamelCase			,						UpperCamelCase						=  next_term(lowercase					, 20					, i + dn					, lowercase				)
				dn += terms_jumped
				if dn == n - i:
						break

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


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


import pyarrow.parquet as pq
import pytest

from datasets import Audio, Dataset, DatasetDict, Features, NamedSplit, Sequence, Value, config
from datasets.features.image import Image
from datasets.io.parquet import ParquetDatasetReader, ParquetDatasetWriter, get_writer_batch_size

from ..utils import assert_arrow_memory_doesnt_increase, assert_arrow_memory_increases


def    A (      lowercase					, lowercase				)     ->						Optional[int]:
		'''simple docstring'''

		assert isinstance(lowercase					, lowercase				)
		assert dataset.num_rows == 4
		assert dataset.num_columns == 3
		assert dataset.column_names == ["col_1", "col_2", "col_3"]
		for feature, expected_dtype in expected_features.items():
				assert dataset.features[feature].dtype == expected_dtype


@pytest.mark.parametrize('keep_in_memory'					, [False, True]				)
def    A (      lowercase					, lowercase					, lowercase				)     ->						Tuple:
		'''simple docstring'''

		UpperCamelCase						=  tmp_path / 'cache'
		UpperCamelCase						=  {'col_1': 'string', 'col_2': 'int64', 'col_3': 'float64'}
		with assert_arrow_memory_increases() if keep_in_memory else assert_arrow_memory_doesnt_increase():
				UpperCamelCase						=  ParquetDatasetReader(lowercase					, cache_dir=lowercase					, keep_in_memory=lowercase				).read()
		_check_parquet_dataset(lowercase					, lowercase				)


@pytest.mark.parametrize(
    'features'					, [
        None,
        {'col_1': 'string', 'col_2': 'int64', 'col_3': 'float64'},
        {'col_1': 'string', 'col_2': 'string', 'col_3': 'string'},
        {'col_1': 'int32', 'col_2': 'int32', 'col_3': 'int32'},
        {'col_1': 'float32', 'col_2': 'float32', 'col_3': 'float32'},
    ]					, )
def    A (      lowercase					, lowercase					, lowercase				)     ->						Tuple:
		'''simple docstring'''

		UpperCamelCase						=  tmp_path / 'cache'
		UpperCamelCase						=  {'col_1': 'string', 'col_2': 'int64', 'col_3': 'float64'}
		UpperCamelCase						=  features.copy() if features else default_expected_features
		UpperCamelCase						=  (
		    Features({feature: Value(lowercase				) for feature, dtype in features.items()}				) if features is not None else None
		)
		UpperCamelCase						=  ParquetDatasetReader(lowercase					, features=lowercase					, cache_dir=lowercase				).read()
		_check_parquet_dataset(lowercase					, lowercase				)


@pytest.mark.parametrize('split'					, [None, NamedSplit('train'				), 'train', 'test']				)
def    A (      lowercase					, lowercase					, lowercase				)     ->						Optional[int]:
		'''simple docstring'''

		UpperCamelCase						=  tmp_path / 'cache'
		UpperCamelCase						=  {'col_1': 'string', 'col_2': 'int64', 'col_3': 'float64'}
		UpperCamelCase						=  ParquetDatasetReader(lowercase					, cache_dir=lowercase					, split=lowercase				).read()
		_check_parquet_dataset(lowercase					, lowercase				)
		assert dataset.split == split if split else "train"


@pytest.mark.parametrize('path_type'					, [str, list]				)
def    A (      lowercase					, lowercase					, lowercase				)     ->						Union[str, Any]:
		'''simple docstring'''

		if issubclass(lowercase					, lowercase				):
				UpperCamelCase						=  parquet_path
		elif issubclass(lowercase					, lowercase				):
				UpperCamelCase						=  [parquet_path]
		UpperCamelCase						=  tmp_path / 'cache'
		UpperCamelCase						=  {'col_1': 'string', 'col_2': 'int64', 'col_3': 'float64'}
		UpperCamelCase						=  ParquetDatasetReader(lowercase					, cache_dir=lowercase				).read()
		_check_parquet_dataset(lowercase					, lowercase				)


def    A (      lowercase					, lowercase					, lowercase=("train",)				)     ->						Tuple:
		'''simple docstring'''

		assert isinstance(lowercase					, lowercase				)
		for split in splits:
				UpperCamelCase						=  dataset_dict[split]
				assert dataset.num_rows == 4
				assert dataset.num_columns == 3
				assert dataset.column_names == ["col_1", "col_2", "col_3"]
				for feature, expected_dtype in expected_features.items():
						assert dataset.features[feature].dtype == expected_dtype


@pytest.mark.parametrize('keep_in_memory'					, [False, True]				)
def    A (      lowercase					, lowercase					, lowercase				)     ->						Optional[Any]:
		'''simple docstring'''

		UpperCamelCase						=  tmp_path / 'cache'
		UpperCamelCase						=  {'col_1': 'string', 'col_2': 'int64', 'col_3': 'float64'}
		with assert_arrow_memory_increases() if keep_in_memory else assert_arrow_memory_doesnt_increase():
				UpperCamelCase						=  ParquetDatasetReader(
				    {'train': parquet_path}					, cache_dir=lowercase					, keep_in_memory=lowercase				).read()
		_check_parquet_datasetdict(lowercase					, lowercase				)


@pytest.mark.parametrize(
    'features'					, [
        None,
        {'col_1': 'string', 'col_2': 'int64', 'col_3': 'float64'},
        {'col_1': 'string', 'col_2': 'string', 'col_3': 'string'},
        {'col_1': 'int32', 'col_2': 'int32', 'col_3': 'int32'},
        {'col_1': 'float32', 'col_2': 'float32', 'col_3': 'float32'},
    ]					, )
def    A (      lowercase					, lowercase					, lowercase				)     ->						List[Any]:
		'''simple docstring'''

		UpperCamelCase						=  tmp_path / 'cache'
		UpperCamelCase						=  {'col_1': 'string', 'col_2': 'int64', 'col_3': 'float64'}
		UpperCamelCase						=  features.copy() if features else default_expected_features
		UpperCamelCase						=  (
		    Features({feature: Value(lowercase				) for feature, dtype in features.items()}				) if features is not None else None
		)
		UpperCamelCase						=  ParquetDatasetReader({'train': parquet_path}					, features=lowercase					, cache_dir=lowercase				).read()
		_check_parquet_datasetdict(lowercase					, lowercase				)


@pytest.mark.parametrize('split'					, [None, NamedSplit('train'				), 'train', 'test']				)
def    A (      lowercase					, lowercase					, lowercase				)     ->						Union[str, Any]:
		'''simple docstring'''

		if split:
				UpperCamelCase						=  {split: parquet_path}
		else:
				UpperCamelCase						=  'train'
				UpperCamelCase						=  {'train': parquet_path, 'test': parquet_path}
		UpperCamelCase						=  tmp_path / 'cache'
		UpperCamelCase						=  {'col_1': 'string', 'col_2': 'int64', 'col_3': 'float64'}
		UpperCamelCase						=  ParquetDatasetReader(lowercase					, cache_dir=lowercase				).read()
		_check_parquet_datasetdict(lowercase					, lowercase					, splits=list(path.keys()				)				)
		assert all(dataset[split].split == split for split in path.keys()				)


def    A (      lowercase					, lowercase				)     ->						List[Any]:
		'''simple docstring'''

		UpperCamelCase						=  ParquetDatasetWriter(lowercase					, tmp_path / 'foo.parquet'				)
		assert writer.write() > 0
		UpperCamelCase						=  pq.ParquetFile(tmp_path / 'foo.parquet'				)
		UpperCamelCase						=  pf.read()
		assert dataset.data.table == output_table


def    A (      lowercase					, lowercase				)     ->						Optional[int]:
		'''simple docstring'''

		UpperCamelCase						=  str(shared_datadir / 'test_image_rgb.jpg'				)
		UpperCamelCase						=  {'image': [image_path]}
		UpperCamelCase						=  Features({'image': Image()}				)
		UpperCamelCase						=  Dataset.from_dict(lowercase					, features=lowercase				)
		UpperCamelCase						=  ParquetDatasetWriter(lowercase					, tmp_path / 'foo.parquet'				)
		assert writer.write() > 0

		UpperCamelCase						=  Dataset.from_parquet(str(tmp_path / 'foo.parquet'				)				)
		assert dataset.features == reloaded_dataset.features

		UpperCamelCase						=  ParquetDatasetReader(str(tmp_path / 'foo.parquet'				)					, streaming=lowercase				).read()
		assert dataset.features == reloaded_iterable_dataset.features


@pytest.mark.parametrize(
    'feature, expected'					, [
        (Features({'foo': Value('int32'				)}				), None),
        (Features({'image': Image(), 'foo': Value('int32'				)}				), config.PARQUET_ROW_GROUP_SIZE_FOR_IMAGE_DATASETS),
        (Features({'nested': Sequence(Audio()				)}				), config.PARQUET_ROW_GROUP_SIZE_FOR_AUDIO_DATASETS),
    ]					, )
def    A (      lowercase					, lowercase				)     ->						Union[str, Any]:
		'''simple docstring'''

		assert get_writer_batch_size(lowercase				) == expected
