
from __future__ import annotations

import math
import random
from collections.abc import Collection
from typing import overload







class  UpperCamelCase__		:







	'''simple docstring'''





	def __init__(			self				,       UpperCamelCase__ = None		):
					if components is None:
									A__  :	Optional[int]         =							[]
					A__  :	Dict         =							list(UpperCamelCase__		)





	def __len__(			self		):
					return len(self.__components		)





	def __str__(			self		):
					return "(" + ",".join(map(UpperCamelCase__				,       self.__components		)		) + ")"





	def __add__(			self				,       UpperCamelCase__		):
					A__  :	Optional[int]         =							len(self		)
					if size == len(UpperCamelCase__		):
									A__  :	Optional[int]         =							[self.__components[i] + other.component(UpperCamelCase__		) for i in range(UpperCamelCase__		)]
									return Vector(UpperCamelCase__		)
					else:
									raise Exception('''must have the same size'''		)





	def __sub__(			self				,       UpperCamelCase__		):
					A__  :	Optional[Any]         =							len(self		)
					if size == len(UpperCamelCase__		):
									A__  :	List[Any]         =							[self.__components[i] - other.component(UpperCamelCase__		) for i in range(UpperCamelCase__		)]
									return Vector(UpperCamelCase__		)
					else:  # error case
									raise Exception('''must have the same size'''		)





	@overload
	def __mul__(			self				,       UpperCamelCase__		):
					...





	@overload
	def __mul__(			self				,       UpperCamelCase__		):
					...





	def __mul__(			self				,       UpperCamelCase__		):
					if isinstance(UpperCamelCase__				,       (float, int)		):
									A__  :	Optional[Any]         =							[c * other for c in self.__components]
									return Vector(UpperCamelCase__		)
					elif isinstance(UpperCamelCase__				,       UpperCamelCase__		) and len(self		) == len(UpperCamelCase__		):
									A__  :	Optional[int]         =							len(self		)
									A__  :	List[Any]         =							[self.__components[i] * other.component(UpperCamelCase__		) for i in range(UpperCamelCase__		)]
									return sum(UpperCamelCase__		)
					else:  # error case
									raise Exception('''invalid operand!'''		)





	def   __snake_case				(			self		):
					return Vector(self.__components		)





	def   __snake_case				(			self				,       UpperCamelCase__		):
					if isinstance(UpperCamelCase__				,       UpperCamelCase__		) and -len(self.__components		) <= i < len(self.__components		):
									return self.__components[i]
					else:
									raise Exception('''index out of range'''		)





	def   __snake_case				(			self				,       UpperCamelCase__				,       UpperCamelCase__		):
					assert -len(self.__components		) <= pos < len(self.__components		)
					A__  :	Tuple         =							value





	def   __snake_case				(			self		):
					if len(self.__components		) == 0:
									raise Exception('''Vector is empty'''		)
					A__  :	Tuple         =							[c**2 for c in self.__components]
					return math.sqrt(sum(UpperCamelCase__		)		)





	def   __snake_case				(			self				,       UpperCamelCase__				,       UpperCamelCase__ = False		):
					A__  :	Dict         =							self * other
					A__  :	Any         =							self.euclidean_length() * other.euclidean_length()
					if deg:
									return math.degrees(math.acos(num / den		)		)
					else:
									return math.acos(num / den		)




def 				SCREAMING_SNAKE_CASE     (      __UpperCamelCase :						int       ) ->       Vector:

				"""simple docstring"""







				assert isinstance(__UpperCamelCase							,						__UpperCamelCase       )
				return Vector([0] * dimension       )

def 				SCREAMING_SNAKE_CASE     (      __UpperCamelCase :						int							,						__UpperCamelCase :						int       ) ->       Vector:

				"""simple docstring"""







				assert isinstance(__UpperCamelCase							,						__UpperCamelCase       ) and (isinstance(__UpperCamelCase							,						__UpperCamelCase       ))
				A__  :	Union[str, Any]         =							[0] * dimension
				A__  :	str         =							1
				return Vector(__UpperCamelCase       )

def 				SCREAMING_SNAKE_CASE     (      __UpperCamelCase :						float							,						__UpperCamelCase :						Vector							,						__UpperCamelCase :						Vector       ) ->       Vector:

				"""simple docstring"""







				assert (
				    isinstance(__UpperCamelCase							,						__UpperCamelCase       )
				    and isinstance(__UpperCamelCase							,						__UpperCamelCase       )
				    and (isinstance(__UpperCamelCase							,						(int, float)       ))
				)
				return x * scalar + y

def 				SCREAMING_SNAKE_CASE     (      __UpperCamelCase :						int							,						__UpperCamelCase :						int							,						__UpperCamelCase :						int       ) ->       Vector:

				"""simple docstring"""







				random.seed(__UpperCamelCase       )
				A__  :	Optional[Any]         =							[random.randint(__UpperCamelCase							,						__UpperCamelCase       ) for _ in range(__UpperCamelCase       )]
				return Vector(__UpperCamelCase       )







class  UpperCamelCase__		:







	'''simple docstring'''





	def __init__(			self				,       UpperCamelCase__				,       UpperCamelCase__				,       UpperCamelCase__		):
					A__  :	Optional[Any]         =							matrix
					A__  :	Optional[int]         =							w
					A__  :	Any         =							h





	def __str__(			self		):
					A__  :	Optional[int]         =							''''''
					for i in range(self.__height		):
									ans += "|"
									for j in range(self.__width		):
													if j < self.__width - 1:
																	ans += str(self.__matrix[i][j]		) + ","
													else:
																	ans += str(self.__matrix[i][j]		) + "|\n"
					return ans





	def __add__(			self				,       UpperCamelCase__		):
					if self.__width == other.width() and self.__height == other.height():
									A__  :	Dict         =							[]
									for i in range(self.__height		):
													A__  :	Any         =							[
													    self.__matrix[i][j] + other.component(UpperCamelCase__				,       UpperCamelCase__		)
													    for j in range(self.__width		)
													]
													matrix.append(UpperCamelCase__		)
									return Matrix(UpperCamelCase__				,       self.__width				,       self.__height		)
					else:
									raise Exception('''matrix must have the same dimension!'''		)





	def __sub__(			self				,       UpperCamelCase__		):
					if self.__width == other.width() and self.__height == other.height():
									A__  :	List[str]         =							[]
									for i in range(self.__height		):
													A__  :	int         =							[
													    self.__matrix[i][j] - other.component(UpperCamelCase__				,       UpperCamelCase__		)
													    for j in range(self.__width		)
													]
													matrix.append(UpperCamelCase__		)
									return Matrix(UpperCamelCase__				,       self.__width				,       self.__height		)
					else:
									raise Exception('''matrices must have the same dimension!'''		)





	@overload
	def __mul__(			self				,       UpperCamelCase__		):
					...





	@overload
	def __mul__(			self				,       UpperCamelCase__		):
					...





	def __mul__(			self				,       UpperCamelCase__		):
					if isinstance(UpperCamelCase__				,       UpperCamelCase__		):  # matrix-vector
									if len(UpperCamelCase__		) == self.__width:
													A__  :	Optional[Any]         =							zero_vector(self.__height		)
													for i in range(self.__height		):
																	A__  :	Optional[Any]         =							[
																	    self.__matrix[i][j] * other.component(UpperCamelCase__		)
																	    for j in range(self.__width		)
																	]
																	ans.change_component(UpperCamelCase__				,       sum(UpperCamelCase__		)		)
													return ans
									else:
													raise Exception(
													    '''vector must have the same size as the '''
													    '''number of columns of the matrix!'''		)
					elif isinstance(UpperCamelCase__				,       (int, float)		):  # matrix-scalar
									A__  :	List[str]         =							[
									    [self.__matrix[i][j] * other for j in range(self.__width		)]
									    for i in range(self.__height		)
									]
									return Matrix(UpperCamelCase__				,       self.__width				,       self.__height		)
					return None





	def   __snake_case				(			self		):
					return self.__height





	def   __snake_case				(			self		):
					return self.__width





	def   __snake_case				(			self				,       UpperCamelCase__				,       UpperCamelCase__		):
					if 0 <= x < self.__height and 0 <= y < self.__width:
									return self.__matrix[x][y]
					else:
									raise Exception('''change_component: indices out of bounds'''		)





	def   __snake_case				(			self				,       UpperCamelCase__				,       UpperCamelCase__				,       UpperCamelCase__		):
					if 0 <= x < self.__height and 0 <= y < self.__width:
									A__  :	Any         =							value
					else:
									raise Exception('''change_component: indices out of bounds'''		)





	def   __snake_case				(			self				,       UpperCamelCase__				,       UpperCamelCase__		):
					if self.__height != self.__width:
									raise Exception('''Matrix is not square'''		)
					A__  :	int         =							self.__matrix[:x] + self.__matrix[x + 1 :]
					for i in range(len(UpperCamelCase__		)		):
									A__  :	Any         =							minor[i][:y] + minor[i][y + 1 :]
					return Matrix(UpperCamelCase__				,       self.__width - 1				,       self.__height - 1		).determinant()





	def   __snake_case				(			self				,       UpperCamelCase__				,       UpperCamelCase__		):
					if self.__height != self.__width:
									raise Exception('''Matrix is not square'''		)
					if 0 <= x < self.__height and 0 <= y < self.__width:
									return (-1) ** (x + y) * self.minor(UpperCamelCase__				,       UpperCamelCase__		)
					else:
									raise Exception('''Indices out of bounds'''		)





	def   __snake_case				(			self		):
					if self.__height != self.__width:
									raise Exception('''Matrix is not square'''		)
					if self.__height < 1:
									raise Exception('''Matrix has no element'''		)
					elif self.__height == 1:
									return self.__matrix[0][0]
					elif self.__height == 2:
									return (
									    self.__matrix[0][0] * self.__matrix[1][1]
									    - self.__matrix[0][1] * self.__matrix[1][0]
									)
					else:
									A__  :	Dict         =							[
									    self.__matrix[0][y] * self.cofactor(0				,       UpperCamelCase__		) for y in range(self.__width		)
									]
									return sum(UpperCamelCase__		)




def 				SCREAMING_SNAKE_CASE     (      __UpperCamelCase :						int       ) ->       Matrix:

				"""simple docstring"""







				A__  :	list[list[float]]         =							[[0] * n for _ in range(__UpperCamelCase       )]
				return Matrix(__UpperCamelCase							,						__UpperCamelCase							,						__UpperCamelCase       )



def 				SCREAMING_SNAKE_CASE     (      __UpperCamelCase :						int							,						__UpperCamelCase :						int							,						__UpperCamelCase :						int							,						__UpperCamelCase :						int       ) ->       Matrix:

				"""simple docstring"""







				random.seed(__UpperCamelCase       )
				A__  :	list[list[float]]         =							[
				    [random.randint(__UpperCamelCase							,						__UpperCamelCase       ) for _ in range(__UpperCamelCase       )] for _ in range(__UpperCamelCase       )
				]
				return Matrix(__UpperCamelCase							,						__UpperCamelCase							,						__UpperCamelCase       )

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

def 				SCREAMING_SNAKE_CASE     (      __UpperCamelCase :						Any							,						__UpperCamelCase :						Dict							,						__UpperCamelCase :						Any							,						__UpperCamelCase :						Optional[Any]       ) ->       int:

				"""simple docstring"""







				A__  :	Tuple         =							sum(a_i[j] for j in range(__UpperCamelCase							,						len(__UpperCamelCase       )       )       )
				A__  :	Tuple         =							sum(a_i[j] * base[j] for j in range(min(len(__UpperCamelCase       )							,						__UpperCamelCase       )       )       )

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

				A__  :	Any         =							memo.get(__UpperCamelCase       )

				if sub_memo is not None:
								A__  :	Optional[int]         =							sub_memo.get(__UpperCamelCase       )

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

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

								else:
												A__  :	List[Any]         =							[]
				else:
								A__  :	Optional[Any]         =							{c: []}
								A__  :	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
												A__       ,							A__  :	str         =							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
								A__       ,							A__  :	str         =							compute(__UpperCamelCase							,						__UpperCamelCase							,						i + dn							,						__UpperCamelCase       )
								diff += _diff
								dn += terms_jumped

				A__  :	str         =							sub_memo[c]

				# keep jumps sorted by # of terms skipped
				A__  :	List[Any]         =							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 				SCREAMING_SNAKE_CASE     (      __UpperCamelCase :						int							,						__UpperCamelCase :						Optional[int]							,						__UpperCamelCase :						List[str]							,						__UpperCamelCase :						int       ) ->       Any:

				"""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)
				A__  :	Optional[Any]         =							i
				A__       ,							A__       ,							A__  :	Dict         =							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
								A__  :	int         =							ds_c + ds_b
								diff += addend
								A__  :	List[Any]         =							0
								for j in range(__UpperCamelCase       ):
												A__  :	Optional[Any]         =							a_i[j] + addend
												A__       ,							A__  :	List[str]         =							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 				SCREAMING_SNAKE_CASE     (      __UpperCamelCase :						Dict							,						__UpperCamelCase :						List[Any]							,						__UpperCamelCase :						int       ) ->       Tuple:

				"""simple docstring"""







				for j in range(__UpperCamelCase							,						len(__UpperCamelCase       )       ):
								A__  :	Any         =							digits[j] + addend
								if s >= 10:
												A__       ,							A__  :	Union[str, Any]         =							divmod(__UpperCamelCase							,						10       )
												A__  :	Optional[int]         =							addend // 10 + quotient
								else:
												A__  :	Any         =							s
												A__  :	Dict         =							addend // 10

								if addend == 0:
												break

				while addend > 0:
								A__       ,							A__  :	Dict         =							divmod(__UpperCamelCase							,						10       )
								digits.append(__UpperCamelCase       )

def 				SCREAMING_SNAKE_CASE     (      __UpperCamelCase :						int = 10**15       ) ->       int:

				"""simple docstring"""







				A__  :	List[Any]         =							[1]
				A__  :	Dict         =							1
				A__  :	Tuple         =							0
				while True:
								A__       ,							A__  :	List[str]         =							next_term(__UpperCamelCase							,						20							,						i + dn							,						__UpperCamelCase       )
								dn += terms_jumped
								if dn == n - i:
												break

				A__  :	List[str]         =							0
				for j in range(len(__UpperCamelCase       )       ):
								a_n += digits[j] * 10**j
				return a_n


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