



'''simple docstring'''



lowerCAmelCase	:		Optional[int]				=   range(2, 2_0 + 1)
lowerCAmelCase	:		List[str]				=   [1_0**k for k in range(ks[-1] + 1)]
lowerCAmelCase	:		dict[int, dict[int, list[list[int]]]]				=   {}



def   __lowerCAmelCase					(							lowerCamelCase   :						Tuple				,		lowerCamelCase   :						Optional[int]				,		lowerCamelCase   :						int				,		lowerCamelCase   :						Union[str, Any]					):






	'''simple docstring'''




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

	__lowerCAmelCase							,       __lowerCAmelCase												=  0, 0
	__lowerCAmelCase												=  n - i

	__lowerCAmelCase												=  memo.get(lowerCamelCase					)

	if sub_memo is not None:
		__lowerCAmelCase												=  sub_memo.get(lowerCamelCase					)

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

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

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

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

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

	__lowerCAmelCase												=  sub_memo[c]

	# keep jumps sorted by # of terms skipped
	__lowerCAmelCase												=  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   __lowerCAmelCase					(							lowerCamelCase   :						Any				,		lowerCamelCase   :						Any				,		lowerCamelCase   :						int				,		lowerCamelCase   :						Optional[Any]					):






	'''simple docstring'''




	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)
	__lowerCAmelCase												=  i
	__lowerCAmelCase							,       __lowerCAmelCase							,       __lowerCAmelCase												=  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
		__lowerCAmelCase												=  ds_c + ds_b
		diff += addend
		__lowerCAmelCase												=  0
		for j in range(lowerCamelCase					):
			__lowerCAmelCase												=  a_i[j] + addend
			__lowerCAmelCase							,       __lowerCAmelCase												=  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   __lowerCAmelCase					(							lowerCamelCase   :						Tuple				,		lowerCamelCase   :						Dict				,		lowerCamelCase   :						int					):






	'''simple docstring'''




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

		if addend == 0:
			break

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



def   __lowerCAmelCase					(							lowerCamelCase   :						int = 10**15					):






	'''simple docstring'''




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

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


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




'''simple docstring'''



from __future__ import annotations

import math



def   __lowerCAmelCase					(							lowerCamelCase   :						list				,		lowerCamelCase   :						list					):






	'''simple docstring'''




	if len(lowerCamelCase					) != 2 or len(a[0]					) != 2 or len(lowerCamelCase					) != 2 or len(b[0]					) != 2:
		raise Exception("Matrices are not 2x2"					)
	__lowerCAmelCase												=  [
	    [a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
	    [a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]],
	]
	return new_matrix



def   __lowerCAmelCase					(							lowerCamelCase   :						list				,		lowerCamelCase   :						list					):






	'''simple docstring'''




	return [
	    [matrix_a[row][col] + matrix_b[row][col] for col in range(len(matrix_a[row]					)					)]
	    for row in range(len(lowerCamelCase					)					)
	]



def   __lowerCAmelCase					(							lowerCamelCase   :						list				,		lowerCamelCase   :						list					):






	'''simple docstring'''




	return [
	    [matrix_a[row][col] - matrix_b[row][col] for col in range(len(matrix_a[row]					)					)]
	    for row in range(len(lowerCamelCase					)					)
	]



def   __lowerCAmelCase					(							lowerCamelCase   :						list					):






	'''simple docstring'''




	if len(lowerCamelCase					) % 2 != 0 or len(a[0]					) % 2 != 0:
		raise Exception("Odd matrices are not supported!"					)

	__lowerCAmelCase												=  len(lowerCamelCase					)
	__lowerCAmelCase												=  matrix_length // 2

	__lowerCAmelCase												=  [[a[i][j] for j in range(lowerCamelCase				,		lowerCamelCase					)] for i in range(lowerCamelCase					)]
	__lowerCAmelCase												=  [
	    [a[i][j] for j in range(lowerCamelCase				,		lowerCamelCase					)] for i in range(lowerCamelCase				,		lowerCamelCase					)
	]

	__lowerCAmelCase												=  [[a[i][j] for j in range(lowerCamelCase					)] for i in range(lowerCamelCase					)]
	__lowerCAmelCase												=  [[a[i][j] for j in range(lowerCamelCase					)] for i in range(lowerCamelCase				,		lowerCamelCase					)]

	return top_left, top_right, bot_left, bot_right



def   __lowerCAmelCase					(							lowerCamelCase   :						list					):






	'''simple docstring'''




	return len(lowerCamelCase					), len(matrix[0]					)



def   __lowerCAmelCase					(							lowerCamelCase   :						list					):






	'''simple docstring'''




	print("\n".join(str(lowerCamelCase					) for line in matrix					)					)



def   __lowerCAmelCase					(							lowerCamelCase   :						list				,		lowerCamelCase   :						list					):






	'''simple docstring'''




	if matrix_dimensions(lowerCamelCase					) == (2, 2):
		return default_matrix_multiplication(lowerCamelCase				,		lowerCamelCase					)

	__lowerCAmelCase							,       __lowerCAmelCase							,       __lowerCAmelCase							,       __lowerCAmelCase												=  split_matrix(lowerCamelCase					)
	__lowerCAmelCase							,       __lowerCAmelCase							,       __lowerCAmelCase							,       __lowerCAmelCase												=  split_matrix(lowerCamelCase					)

	__lowerCAmelCase												=  actual_strassen(lowerCamelCase				,		matrix_subtraction(lowerCamelCase				,		lowerCamelCase					)					)
	__lowerCAmelCase												=  actual_strassen(matrix_addition(lowerCamelCase				,		lowerCamelCase					)				,		lowerCamelCase					)
	__lowerCAmelCase												=  actual_strassen(matrix_addition(lowerCamelCase				,		lowerCamelCase					)				,		lowerCamelCase					)
	__lowerCAmelCase												=  actual_strassen(lowerCamelCase				,		matrix_subtraction(lowerCamelCase				,		lowerCamelCase					)					)
	__lowerCAmelCase												=  actual_strassen(matrix_addition(lowerCamelCase				,		lowerCamelCase					)				,		matrix_addition(lowerCamelCase				,		lowerCamelCase					)					)
	__lowerCAmelCase												=  actual_strassen(matrix_subtraction(lowerCamelCase				,		lowerCamelCase					)				,		matrix_addition(lowerCamelCase				,		lowerCamelCase					)					)
	__lowerCAmelCase												=  actual_strassen(matrix_subtraction(lowerCamelCase				,		lowerCamelCase					)				,		matrix_addition(lowerCamelCase				,		lowerCamelCase					)					)

	__lowerCAmelCase												=  matrix_addition(matrix_subtraction(matrix_addition(lowerCamelCase				,		lowerCamelCase					)				,		lowerCamelCase					)				,		lowerCamelCase					)
	__lowerCAmelCase												=  matrix_addition(lowerCamelCase				,		lowerCamelCase					)
	__lowerCAmelCase												=  matrix_addition(lowerCamelCase				,		lowerCamelCase					)
	__lowerCAmelCase												=  matrix_subtraction(matrix_subtraction(matrix_addition(lowerCamelCase				,		lowerCamelCase					)				,		lowerCamelCase					)				,		lowerCamelCase					)

	# construct the new matrix from our 4 quadrants
	__lowerCAmelCase												=  []
	for i in range(len(lowerCamelCase					)					):
		new_matrix.append(top_left[i] + top_right[i]					)
	for i in range(len(lowerCamelCase					)					):
		new_matrix.append(bot_left[i] + bot_right[i]					)
	return new_matrix



def   __lowerCAmelCase					(							lowerCamelCase   :						list				,		lowerCamelCase   :						list					):






	'''simple docstring'''




	if matrix_dimensions(lowerCamelCase					)[1] != matrix_dimensions(lowerCamelCase					)[0]:
		__lowerCAmelCase												=  (
		    "Unable to multiply these matrices, please check the dimensions.\n"
		    f'''Matrix A: {matrixa}\n'''
		    f'''Matrix B: {matrixa}'''
		)
		raise Exception(lowerCamelCase					)
	__lowerCAmelCase												=  matrix_dimensions(lowerCamelCase					)
	__lowerCAmelCase												=  matrix_dimensions(lowerCamelCase					)

	if dimensiona[0] == dimensiona[1] and dimensiona[0] == dimensiona[1]:
		return [matrixa, matrixa]

	__lowerCAmelCase												=  max(*lowerCamelCase				,		*lowerCamelCase					)
	__lowerCAmelCase												=  int(math.pow(2				,		math.ceil(math.loga(lowerCamelCase					)					)					)					)
	__lowerCAmelCase												=  matrixa
	__lowerCAmelCase												=  matrixa

	# Adding zeros to the matrices so that the arrays dimensions are the same and also
	# power of 2
	for i in range(0				,		lowerCamelCase					):
		if i < dimensiona[0]:
			for _ in range(dimensiona[1]				,		lowerCamelCase					):
				new_matrixa[i].append(0					)
		else:
			new_matrixa.append([0] * maxim					)
		if i < dimensiona[0]:
			for _ in range(dimensiona[1]				,		lowerCamelCase					):
				new_matrixa[i].append(0					)
		else:
			new_matrixa.append([0] * maxim					)

	__lowerCAmelCase												=  actual_strassen(lowerCamelCase				,		lowerCamelCase					)

	# Removing the additional zeros
	for i in range(0				,		lowerCamelCase					):
		if i < dimensiona[0]:
			for _ in range(dimensiona[1]				,		lowerCamelCase					):
				final_matrix[i].pop()
		else:
			final_matrix.pop()
	return final_matrix


if __name__ == "__main__":
	lowerCAmelCase	:		Tuple				=   [
	    [2, 3, 4, 5],
	    [6, 4, 3, 1],
	    [2, 3, 6, 7],
	    [3, 1, 2, 4],
	    [2, 3, 4, 5],
	    [6, 4, 3, 1],
	    [2, 3, 6, 7],
	    [3, 1, 2, 4],
	    [2, 3, 4, 5],
	    [6, 2, 3, 1],
	]
	lowerCAmelCase	:		Any				=   [[0, 2, 1, 1], [1_6, 2, 3, 3], [2, 2, 7, 7], [1_3, 1_1, 2_2, 4]]
	print(strassen(matrixa, matrixa))