


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


def 		lowercase_  (     _UpperCamelCase       ,			_UpperCamelCase       ,			_UpperCamelCase       ,			_UpperCamelCase  ):


			'''simple docstring'''







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

			__lowercase					, __lowercase 					=   0, 0
			__lowercase 					=   n - i

			__lowercase 					=   memo.get(_UpperCamelCase  )

			if sub_memo is not None:
						__lowercase 					=   sub_memo.get(_UpperCamelCase  )

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

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

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

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

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

			__lowercase 					=   sub_memo[c]

			# keep jumps sorted by # of terms skipped
			__lowercase 					=   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 		lowercase_  (     _UpperCamelCase       ,			_UpperCamelCase       ,			_UpperCamelCase       ,			_UpperCamelCase  ):


			'''simple docstring'''







			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)
			__lowercase 					=   i
			__lowercase					, __lowercase					, __lowercase 					=   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
						__lowercase 					=   ds_c + ds_b
						diff += addend
						__lowercase 					=   0
						for j in range(_UpperCamelCase  ):
									__lowercase 					=   a_i[j] + addend
									__lowercase					, __lowercase 					=   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 		lowercase_  (     _UpperCamelCase       ,			_UpperCamelCase       ,			_UpperCamelCase  ):


			'''simple docstring'''







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

						if addend == 0:
									break

			while addend > 0:
						__lowercase					, __lowercase 					=   divmod(_UpperCamelCase       ,			10  )
						digits.append(_UpperCamelCase  )


def 		lowercase_  (     _UpperCamelCase = 10**15  ):


			'''simple docstring'''







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

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


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






def 		lowercase_  (     _UpperCamelCase  ):


			'''simple docstring'''







			__lowercase 					=   len(_UpperCamelCase  )
			__lowercase 					=   len(matrix[0]  )
			__lowercase 					=   min(_UpperCamelCase       ,			_UpperCamelCase  )

			for row in range(_UpperCamelCase  ):
						# Check if diagonal element is not zero
						if matrix[row][row] != 0:
									# Eliminate all the elements below the diagonal
									for col in range(row + 1       ,			_UpperCamelCase  ):
												__lowercase 					=   matrix[col][row] / matrix[row][row]
												for i in range(_UpperCamelCase       ,			_UpperCamelCase  ):
															matrix[col][i] -= multiplier * matrix[row][i]
						else:
									# Find a non-zero diagonal element to swap rows
									__lowercase 					=   True
									for i in range(row + 1       ,			_UpperCamelCase  ):
												if matrix[i][row] != 0:
															__lowercase					, __lowercase 					=   matrix[i], matrix[row]
															__lowercase 					=   False
															break
									if reduce:
												rank -= 1
												for i in range(_UpperCamelCase  ):
															__lowercase 					=   matrix[i][rank]

            # Reduce the row pointer by one to stay on the same row
									row -= 1

			return rank


if __name__ == "__main__":
	import doctest

	doctest.testmod()


