






"""simple docstring"""

from __future__ import annotations

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

class 						A_							:







				def __init__(							self							:						Any						,    __lowerCamelCase							:						Collection[float] | None = None	)				->					None:
										if components is None:
																__magic_name__            =     []
										__magic_name__            =     list(__lowerCamelCase	)







				def __len__(							self							:						Optional[Any]	)				->					int:
										return len(self.__components	)







				def __str__(							self							:						str	)				->					str:
										return "(" + ",".join(map(__lowerCamelCase						,    self.__components	)	) + ")"







				def __add__(							self							:						str						,    __lowerCamelCase							:						Vector	)				->					Vector:
										__magic_name__            =     len(self	)
										if size == len(__lowerCamelCase	):
																__magic_name__            =     [self.__components[i] + other.component(__lowerCamelCase	) for i in range(__lowerCamelCase	)]
																return Vector(__lowerCamelCase	)
										else:
																raise Exception("must have the same size"	)







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







				@overload
				def __mul__(							self							:						int						,    __lowerCamelCase							:						float	)				->					Vector:
										...







				@overload
				def __mul__(							self							:						int						,    __lowerCamelCase							:						Vector	)				->					float:
										...







				def __mul__(							self							:						Dict						,    __lowerCamelCase							:						float | Vector	)				->					float | Vector:
										if isinstance(__lowerCamelCase						,    (float, int)	):
																__magic_name__            =     [c * other for c in self.__components]
																return Vector(__lowerCamelCase	)
										elif isinstance(__lowerCamelCase						,    __lowerCamelCase	) and len(self	) == len(__lowerCamelCase	):
																__magic_name__            =     len(self	)
																__magic_name__            =     [self.__components[i] * other.component(__lowerCamelCase	) for i in range(__lowerCamelCase	)]
																return sum(__lowerCamelCase	)
										else:  # error case
																raise Exception("invalid operand!"	)







				def     _snake_case					(							self							:						List[Any]	)				->					Vector:
										return Vector(self.__components	)







				def     _snake_case					(							self							:						Optional[int]						,    __lowerCamelCase							:						int	)				->					float:
										if isinstance(__lowerCamelCase						,    __lowerCamelCase	) and -len(self.__components	) <= i < len(self.__components	):
																return self.__components[i]
										else:
																raise Exception("index out of range"	)







				def     _snake_case					(							self							:						Any						,    __lowerCamelCase							:						int						,    __lowerCamelCase							:						float	)				->					None:
										assert -len(self.__components	) <= pos < len(self.__components	)
										__magic_name__            =     value







				def     _snake_case					(							self							:						List[Any]	)				->					float:
										if len(self.__components	) == 0:
																raise Exception("Vector is empty"	)
										__magic_name__            =     [c**2 for c in self.__components]
										return math.sqrt(sum(__lowerCamelCase	)	)







				def     _snake_case					(							self							:						Union[str, Any]						,    __lowerCamelCase							:						Vector						,    __lowerCamelCase							:						bool = False	)				->					float:
										__magic_name__            =     self * other
										__magic_name__            =     self.euclidean_length() * other.euclidean_length()
										if deg:
																return math.degrees(math.acos(num / den	)	)
										else:
																return math.acos(num / den	)






def _lowerCAmelCase	(  __lowerCamelCase:int   ):

						'''simple docstring'''






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






def _lowerCAmelCase	(  __lowerCamelCase:int ,						__lowerCamelCase:int   ):

						'''simple docstring'''






						assert isinstance(__lowerCamelCase ,						__lowerCamelCase   ) and (isinstance(__lowerCamelCase ,						__lowerCamelCase   ))
						__magic_name__            =     [0] * dimension
						__magic_name__            =     1
						return Vector(__lowerCamelCase   )






def _lowerCAmelCase	(  __lowerCamelCase:float ,						__lowerCamelCase:Vector ,						__lowerCamelCase:Vector   ):

						'''simple docstring'''






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






def _lowerCAmelCase	(  __lowerCamelCase:int ,						__lowerCamelCase:int ,						__lowerCamelCase:int   ):

						'''simple docstring'''






						random.seed(__lowerCamelCase   )
						__magic_name__            =     [random.randint(__lowerCamelCase ,						__lowerCamelCase   ) for _ in range(__lowerCamelCase   )]
						return Vector(__lowerCamelCase   )

class 						A_							:







				def __init__(							self							:						Tuple						,    __lowerCamelCase							:						list[list[float]]						,    __lowerCamelCase							:						int						,    __lowerCamelCase							:						int	)				->					None:
										__magic_name__            =     matrix
										__magic_name__            =     w
										__magic_name__            =     h







				def __str__(							self							:						Union[str, Any]	)				->					str:
										__magic_name__            =     ""
										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							:						Union[str, Any]						,    __lowerCamelCase							:						Matrix	)				->					Matrix:
										if self.__width == other.width() and self.__height == other.height():
																__magic_name__            =     []
																for i in range(self.__height	):
																						__magic_name__            =     [
																						    self.__matrix[i][j] + other.component(__lowerCamelCase						,    __lowerCamelCase	)
																						    for j in range(self.__width	)
																						]
																						matrix.append(__lowerCamelCase	)
																return Matrix(__lowerCamelCase						,    self.__width						,    self.__height	)
										else:
																raise Exception("matrix must have the same dimension!"	)







				def __sub__(							self							:						Tuple						,    __lowerCamelCase							:						Matrix	)				->					Matrix:
										if self.__width == other.width() and self.__height == other.height():
																__magic_name__            =     []
																for i in range(self.__height	):
																						__magic_name__            =     [
																						    self.__matrix[i][j] - other.component(__lowerCamelCase						,    __lowerCamelCase	)
																						    for j in range(self.__width	)
																						]
																						matrix.append(__lowerCamelCase	)
																return Matrix(__lowerCamelCase						,    self.__width						,    self.__height	)
										else:
																raise Exception("matrices must have the same dimension!"	)







				@overload
				def __mul__(							self							:						List[Any]						,    __lowerCamelCase							:						float	)				->					Matrix:
										...







				@overload
				def __mul__(							self							:						Union[str, Any]						,    __lowerCamelCase							:						Vector	)				->					Vector:
										...







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







				def     _snake_case					(							self							:						Tuple	)				->					int:
										return self.__height







				def     _snake_case					(							self							:						Any	)				->					int:
										return self.__width







				def     _snake_case					(							self							:						Optional[Any]						,    __lowerCamelCase							:						int						,    __lowerCamelCase							:						int	)				->					float:
										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							:						Union[str, Any]						,    __lowerCamelCase							:						int						,    __lowerCamelCase							:						int						,    __lowerCamelCase							:						float	)				->					None:
										if 0 <= x < self.__height and 0 <= y < self.__width:
																__magic_name__            =     value
										else:
																raise Exception("change_component: indices out of bounds"	)







				def     _snake_case					(							self							:						Optional[int]						,    __lowerCamelCase							:						int						,    __lowerCamelCase							:						int	)				->					float:
										if self.__height != self.__width:
																raise Exception("Matrix is not square"	)
										__magic_name__            =     self.__matrix[:x] + self.__matrix[x + 1 :]
										for i in range(len(__lowerCamelCase	)	):
																__magic_name__            =     minor[i][:y] + minor[i][y + 1 :]
										return Matrix(__lowerCamelCase						,    self.__width - 1						,    self.__height - 1	).determinant()







				def     _snake_case					(							self							:						Optional[Any]						,    __lowerCamelCase							:						int						,    __lowerCamelCase							:						int	)				->					float:
										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(__lowerCamelCase						,    __lowerCamelCase	)
										else:
																raise Exception("Indices out of bounds"	)







				def     _snake_case					(							self							:						List[Any]	)				->					float:
										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:
																__magic_name__            =     [
																    self.__matrix[0][y] * self.cofactor(0						,    __lowerCamelCase	) for y in range(self.__width	)
																]
																return sum(__lowerCamelCase	)






def _lowerCAmelCase	(  __lowerCamelCase:int   ):

						'''simple docstring'''






						__magic_name__            =     [[0] * n for _ in range(__lowerCamelCase   )]
						return Matrix(__lowerCamelCase ,						__lowerCamelCase ,						__lowerCamelCase   )






def _lowerCAmelCase	(  __lowerCamelCase:int ,						__lowerCamelCase:int ,						__lowerCamelCase:int ,						__lowerCamelCase:int   ):

						'''simple docstring'''






						random.seed(__lowerCamelCase   )
						__magic_name__            =     [
						    [random.randint(__lowerCamelCase ,						__lowerCamelCase   ) for _ in range(__lowerCamelCase   )] for _ in range(__lowerCamelCase   )
						]
						return Matrix(__lowerCamelCase ,						__lowerCamelCase ,						__lowerCamelCase   )











"""simple docstring"""

from copy import deepcopy

class 						A_							:







				def __init__(							self							:						List[str]						,    __lowerCamelCase							:						list[int] | None = None						,    __lowerCamelCase							:						int | None = None	)				->					None:

										if arr is None and size is not None:
																__magic_name__            =     size
																__magic_name__            =     [0] * size
										elif arr is not None:
																self.init(__lowerCamelCase	)
										else:
																raise ValueError("Either arr or size must be specified"	)







				def     _snake_case					(							self							:						Optional[int]						,    __lowerCamelCase							:						list[int]	)				->					None:
										__magic_name__            =     len(__lowerCamelCase	)
										__magic_name__            =     deepcopy(__lowerCamelCase	)
										for i in range(1						,    self.size	):
																__magic_name__            =     self.next_(__lowerCamelCase	)
																if j < self.size:
																						self.tree[j] += self.tree[i]







				def     _snake_case					(							self							:						Any	)				->					list[int]:
										__magic_name__            =     self.tree[:]
										for i in range(self.size - 1						,    0						,    -1	):
																__magic_name__            =     self.next_(__lowerCamelCase	)
																if j < self.size:
																						arr[j] -= arr[i]
										return arr







				@staticmethod
				def     _snake_case					(							__lowerCamelCase							:						int	)				->					int:
										return index + (index & (-index))







				@staticmethod
				def     _snake_case					(							__lowerCamelCase							:						int	)				->					int:
										return index - (index & (-index))







				def     _snake_case					(							self							:						Union[str, Any]						,    __lowerCamelCase							:						int						,    __lowerCamelCase							:						int	)				->					None:
										if index == 0:
																self.tree[0] += value
																return
										while index < self.size:
																self.tree[index] += value
																__magic_name__            =     self.next_(__lowerCamelCase	)







				def     _snake_case					(							self							:						Any						,    __lowerCamelCase							:						int						,    __lowerCamelCase							:						int	)				->					None:
										self.add(__lowerCamelCase						,    value - self.get(__lowerCamelCase	)	)







				def     _snake_case					(							self							:						List[Any]						,    __lowerCamelCase							:						int	)				->					int:
										if right == 0:
																return 0
										__magic_name__            =     self.tree[0]
										right -= 1  # make right inclusive
										while right > 0:
																result += self.tree[right]
																__magic_name__            =     self.prev(__lowerCamelCase	)
										return result







				def     _snake_case					(							self							:						Any						,    __lowerCamelCase							:						int						,    __lowerCamelCase							:						int	)				->					int:
										return self.prefix(__lowerCamelCase	) - self.prefix(__lowerCamelCase	)







				def     _snake_case					(							self							:						Tuple						,    __lowerCamelCase							:						int	)				->					int:
										return self.query(__lowerCamelCase						,    index + 1	)







				def     _snake_case					(							self							:						Tuple						,    __lowerCamelCase							:						int	)				->					int:
										value -= self.tree[0]
										if value < 0:
																return -1

										__magic_name__            =     1  # Largest power of 2 <= size
										while j * 2 < self.size:
																j *= 2

										__magic_name__            =     0

										while j > 0:
																if i + j < self.size and self.tree[i + j] <= value:
																						value -= self.tree[i + j]
																						i += j
																j //= 2
										return i


if __name__ == "__main__":
			import doctest

			doctest.testmod()



