

"""simple docstring"""
__SCREAMING_SNAKE_CASE							:    Dict		=    range(2, 20 + 1)
__SCREAMING_SNAKE_CASE							:    int		=    [10**k for k in range(ks[-1] + 1)]
__SCREAMING_SNAKE_CASE							:    Union[str, Any]		=    {}







def 						_a				(      _SCREAMING_SNAKE_CASE				, _SCREAMING_SNAKE_CASE				, _SCREAMING_SNAKE_CASE				, _SCREAMING_SNAKE_CASE				)    ->				Optional[int]:
							snake_case_           =		sum(a_i[j] for j in range(a_				, len(a_				)				)				)
							snake_case_           =		sum(a_i[j] * base[j] for j in range(min(len(a_				)				, a_				)				)				)

							snake_case_           =		0, 0
							snake_case_           =		n - i

							snake_case_           =		memo.get(a_				)

							if sub_memo is not None:
														snake_case_           =		sub_memo.get(a_				)

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

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

														else:
																					snake_case_           =		[]
							else:
														snake_case_           =		{c: []}
														snake_case_           =		sub_memo

							if dn >= max_dn or c + diff >= base[k]:
														return diff, dn

							if k > ks[0]:
														while True:
																					# keep doing smaller jumps
																					snake_case_           =		next_term(a_				, k - 1				, i + dn				, a_				)
																					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
														snake_case_           =		compute(a_				, a_				, i + dn				, a_				)
														diff += _diff
														dn += terms_jumped

							snake_case_           =		sub_memo[c]

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

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







def 						_a				(      _SCREAMING_SNAKE_CASE				, _SCREAMING_SNAKE_CASE				, _SCREAMING_SNAKE_CASE				, _SCREAMING_SNAKE_CASE				)    ->				Any:
							if i >= n:
														return 0, i
							if k > len(a_				):
														a_i.extend([0 for _ in range(k - len(a_				)				)]				)

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

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

																					ds_c += a_i[j]

														if addend > 0:
																					break

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







def 						_a				(      _SCREAMING_SNAKE_CASE				, _SCREAMING_SNAKE_CASE				, _SCREAMING_SNAKE_CASE				)    ->				List[str]:
							for j in range(a_				, len(a_				)				):
														snake_case_           =		digits[j] + addend
														if s >= 10:
																					snake_case_           =		divmod(a_				, 10				)
																					snake_case_           =		addend // 10 + quotient
														else:
																					snake_case_           =		s
																					snake_case_           =		addend // 10

														if addend == 0:
																					break

							while addend > 0:
														snake_case_           =		divmod(a_				, 10				)
														digits.append(a_				)







def 						_a				(      _SCREAMING_SNAKE_CASE = 10**15				)    ->				int:
							snake_case_           =		[1]
							snake_case_           =		1
							snake_case_           =		0
							while True:
														snake_case_           =		next_term(a_				, 20				, i + dn				, a_				)
														dn += terms_jumped
														if dn == n - i:
																					break

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


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







"""simple docstring"""
import json
import os
import tempfile
import unittest

import numpy as np
from datasets import load_dataset

from transformers.testing_utils import require_torch, require_vision, slow
from transformers.utils import is_torch_available, is_vision_available

from ...test_image_processing_common import ImageProcessingSavingTestMixin


if is_torch_available():
				import torch

if is_vision_available():
				from PIL import Image

				from transformers import ImageGPTImageProcessor





class      __A     (unittest.TestCase):





							'''simple docstring'''

							def __init__(				self							:      int		,       UpperCAmelCase_							:      List[str]		,       UpperCAmelCase_							:      Tuple=7		,       UpperCAmelCase_							:      Dict=3		,       UpperCAmelCase_							:      Tuple=18		,       UpperCAmelCase_							:      Optional[Any]=30		,       UpperCAmelCase_							:      str=400		,       UpperCAmelCase_							:      int=True		,       UpperCAmelCase_							:      Optional[int]=None		,       UpperCAmelCase_							:      Optional[Any]=True		,       )					->Optional[Any]:



														"""simple docstring"""



														snake_case_           =		size if size is not None else {"""height""": 18, """width""": 18}
														snake_case_           =		parent
														snake_case_           =		batch_size
														snake_case_           =		num_channels
														snake_case_           =		image_size
														snake_case_           =		min_resolution
														snake_case_           =		max_resolution
														snake_case_           =		do_resize
														snake_case_           =		size
														snake_case_           =		do_normalize



							def 		lowerCAmelCase       (				self							:      List[str]       )					->Optional[Any]:



														"""simple docstring"""



														return {
														    # here we create 2 clusters for the sake of simplicity
														    "clusters": np.asarray(
														        [
														            [0.8_866_443_634_033_203, 0.6_618_829_369_544_983, 0.3_891_746_401_786_804],
														            [-0.6_042_559_146_881_104, -0.02_295_008_860_528_469, 0.5_423_797_369_003_296],
														        ]       ),
														    "do_resize": self.do_resize,
														    "size": self.size,
														    "do_normalize": self.do_normalize,
														}





@require_torch
@require_vision
class      __A     (snake_case__						,		unittest.TestCase):





							'''simple docstring'''

							__lowercase:		List[Any]							      =    ImageGPTImageProcessor if is_vision_available() else None



							def 		lowerCAmelCase       (				self							:      Optional[int]       )					->Optional[int]:



														"""simple docstring"""



														snake_case_           =		ImageGPTImageProcessingTester(self       )



							@property
							def 		lowerCAmelCase       (				self							:      Tuple       )					->List[Any]:



														"""simple docstring"""



														return self.image_processor_tester.prepare_image_processor_dict()



							def 		lowerCAmelCase       (				self							:      Optional[Any]       )					->List[str]:



														"""simple docstring"""



														snake_case_           =		self.image_processing_class(**self.image_processor_dict       )
														self.assertTrue(hasattr(UpperCAmelCase_		,       """clusters"""       )       )
														self.assertTrue(hasattr(UpperCAmelCase_		,       """do_resize"""       )       )
														self.assertTrue(hasattr(UpperCAmelCase_		,       """size"""       )       )
														self.assertTrue(hasattr(UpperCAmelCase_		,       """do_normalize"""       )       )



							def 		lowerCAmelCase       (				self							:      Optional[int]       )					->Optional[Any]:



														"""simple docstring"""



														snake_case_           =		self.image_processing_class.from_dict(self.image_processor_dict       )
														self.assertEqual(image_processor.size		,       {"""height""": 18, """width""": 18}       )

														snake_case_           =		self.image_processing_class.from_dict(self.image_processor_dict		,       size=42       )
														self.assertEqual(image_processor.size		,       {"""height""": 42, """width""": 42}       )



							def 		lowerCAmelCase       (				self							:      Any       )					->List[Any]:



														"""simple docstring"""



														snake_case_           =		self.image_processing_class(**self.image_processor_dict       )
														snake_case_           =		json.loads(image_processor.to_json_string()       )
														for key, value in self.image_processor_dict.items():
																					if key == "clusters":
																												self.assertTrue(np.array_equal(UpperCAmelCase_		,       obj[key]       )       )
																					else:
																												self.assertEqual(obj[key]		,       UpperCAmelCase_       )



							def 		lowerCAmelCase       (				self							:      Optional[int]       )					->Dict:



														"""simple docstring"""



														snake_case_           =		self.image_processing_class(**self.image_processor_dict       )

														with tempfile.TemporaryDirectory() as tmpdirname:
																					snake_case_           =		os.path.join(UpperCAmelCase_		,       """image_processor.json"""       )
																					image_processor_first.to_json_file(UpperCAmelCase_       )
																					snake_case_           =		self.image_processing_class.from_json_file(UpperCAmelCase_       ).to_dict()

														snake_case_           =		image_processor_first.to_dict()
														for key, value in image_processor_first.items():
																					if key == "clusters":
																												self.assertTrue(np.array_equal(UpperCAmelCase_		,       image_processor_second[key]       )       )
																					else:
																												self.assertEqual(image_processor_first[key]		,       UpperCAmelCase_       )



							def 		lowerCAmelCase       (				self							:      Optional[Any]       )					->List[Any]:



														"""simple docstring"""



														snake_case_           =		self.image_processing_class(**self.image_processor_dict       )

														with tempfile.TemporaryDirectory() as tmpdirname:
																					image_processor_first.save_pretrained(UpperCAmelCase_       )
																					snake_case_           =		self.image_processing_class.from_pretrained(UpperCAmelCase_       ).to_dict()

														snake_case_           =		image_processor_first.to_dict()
														for key, value in image_processor_first.items():
																					if key == "clusters":
																												self.assertTrue(np.array_equal(UpperCAmelCase_		,       image_processor_second[key]       )       )
																					else:
																												self.assertEqual(image_processor_first[key]		,       UpperCAmelCase_       )



							@unittest.skip("""ImageGPT requires clusters at initialization"""       )
							def 		lowerCAmelCase       (				self							:      List[Any]       )					->Tuple:



														"""simple docstring"""



														pass







def 						_a				(      )    ->				str:
							snake_case_           =		load_dataset("""hf-internal-testing/fixtures_image_utils"""				, split="""test"""				)

							snake_case_           =		Image.open(dataset[4]["""file"""]				)
							snake_case_           =		Image.open(dataset[5]["""file"""]				)

							snake_case_           =		[imagea, imagea]

							return images





@require_vision
@require_torch
class      __A     (unittest.TestCase):





							'''simple docstring'''

							@slow
							def 		lowerCAmelCase       (				self							:      Tuple       )					->List[str]:



														"""simple docstring"""



														snake_case_           =		ImageGPTImageProcessor.from_pretrained("""openai/imagegpt-small"""       )

														snake_case_           =		prepare_images()

														# test non-batched
														snake_case_           =		image_processing(images[0]		,       return_tensors="""pt"""       )

														self.assertIsInstance(encoding.input_ids		,       torch.LongTensor       )
														self.assertEqual(encoding.input_ids.shape		,       (1, 1_024)       )

														snake_case_           =		[306, 191, 191]
														self.assertEqual(encoding.input_ids[0, :3].tolist()		,       UpperCAmelCase_       )

														# test batched
														snake_case_           =		image_processing(UpperCAmelCase_		,       return_tensors="""pt"""       )

														self.assertIsInstance(encoding.input_ids		,       torch.LongTensor       )
														self.assertEqual(encoding.input_ids.shape		,       (2, 1_024)       )

														snake_case_           =		[303, 13, 13]
														self.assertEqual(encoding.input_ids[1, -3:].tolist()		,       UpperCAmelCase_       )



