






"""simple docstring"""


from __future__ import annotations

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




class 						__UpperCamelCase     :
					def __init__(							self							:	Union[str, Any]     , UpperCAmelCase							:	Collection[float] | None = None   )	->       List[Any]:
											if components is None:
																	lowerCAmelCase   :Tuple						=			[]
											lowerCAmelCase   :Optional[int]						=			list(__lowerCamelCase   )
					def __len__(							self							:	str   )	->       Optional[Any]:
											return len(self.__components   )
					def __str__(							self							:	str   )	->       Union[str, Any]:
											return "(" + ",".join(map(__lowerCamelCase     , self.__components   )   ) + ")"
					def __add__(							self							:	int     , UpperCAmelCase							:	Vector   )	->       Union[str, Any]:
											lowerCAmelCase   :int						=			len(self   )
											if size == len(__lowerCamelCase   ):
																	lowerCAmelCase   :Any						=			[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							:	Any     , UpperCAmelCase							:	Vector   )	->       Union[str, Any]:
											lowerCAmelCase   :str						=			len(self   )
											if size == len(__lowerCamelCase   ):
																	lowerCAmelCase   :List[Any]						=			[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							:	Optional[int]     , UpperCAmelCase							:	float   )	->       List[Any]:
											...
					@overload
					def __mul__(							self							:	Optional[Any]     , UpperCAmelCase							:	Vector   )	->       int:
											...
					def __mul__(							self							:	List[Any]     , UpperCAmelCase							:	float | Vector   )	->       Optional[Any]:
											if isinstance(__lowerCamelCase     , (float, int)   ):
																	lowerCAmelCase   :str						=			[c * other for c in self.__components]
																	return Vector(__lowerCamelCase   )
											elif isinstance(__lowerCamelCase     , __lowerCamelCase   ) and len(self   ) == len(__lowerCamelCase   ):
																	lowerCAmelCase   :List[str]						=			len(self   )
																	lowerCAmelCase   :Tuple						=			[self.__components[i] * other.component(__lowerCamelCase   ) for i in range(__lowerCamelCase   )]
																	return sum(__lowerCamelCase   )
											else:  # error case
																	raise Exception('invalid operand!'   )
					def        UpperCAmelCase__ (							self							:	int   )	->       Union[str, Any]:
											return Vector(self.__components   )
					def        UpperCAmelCase__ (							self							:	Tuple     , UpperCAmelCase							:	int   )	->       Any:
											if isinstance(__lowerCamelCase     , __lowerCamelCase   ) and -len(self.__components   ) <= i < len(self.__components   ):
																	return self.__components[i]
											else:
																	raise Exception('index out of range'   )
					def        UpperCAmelCase__ (							self							:	str     , UpperCAmelCase							:	int     , UpperCAmelCase							:	float   )	->       int:
											assert -len(self.__components   ) <= pos < len(self.__components   )
											lowerCAmelCase   :Tuple						=			value
					def        UpperCAmelCase__ (							self							:	Optional[int]   )	->       Dict:
											if len(self.__components   ) == 0:
																	raise Exception('Vector is empty'   )
											lowerCAmelCase   :Optional[Any]						=			[c**2 for c in self.__components]
											return math.sqrt(sum(__lowerCamelCase   )   )
					def        UpperCAmelCase__ (							self							:	Optional[int]     , UpperCAmelCase							:	Vector     , UpperCAmelCase							:	bool = False   )	->       Dict:
											lowerCAmelCase   :int						=			self * other
											lowerCAmelCase   :List[str]						=			self.euclidean_length() * other.euclidean_length()
											if deg:
																	return math.degrees(math.acos(num / den   )   )
											else:
																	return math.acos(num / den   )


def        UpperCAmelCase      (					a__ ):





						'''simple docstring'''






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


def        UpperCAmelCase      (					a__     ,      a__ ):





						'''simple docstring'''






						assert isinstance(lowerCAmelCase_     ,      lowerCAmelCase_ ) and (isinstance(lowerCAmelCase_     ,      lowerCAmelCase_ ))
						lowerCAmelCase   :Dict						=			[0] * dimension
						lowerCAmelCase   :Any						=			1
						return Vector(lowerCAmelCase_ )


def        UpperCAmelCase      (					a__     ,      a__     ,      a__ ):





						'''simple docstring'''






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


def        UpperCAmelCase      (					a__     ,      a__     ,      a__ ):





						'''simple docstring'''






						random.seed(lowerCAmelCase_ )
						lowerCAmelCase   :str						=			[random.randint(lowerCAmelCase_     ,      lowerCAmelCase_ ) for _ in range(lowerCAmelCase_ )]
						return Vector(lowerCAmelCase_ )




class 						__UpperCamelCase     :
					def __init__(							self							:	int     , UpperCAmelCase							:	list[list[float]]     , UpperCAmelCase							:	int     , UpperCAmelCase							:	int   )	->       Optional[Any]:
											lowerCAmelCase   :Dict						=			matrix
											lowerCAmelCase   :Optional[int]						=			w
											lowerCAmelCase   :List[str]						=			h
					def __str__(							self							:	Dict   )	->       str:
											lowerCAmelCase   :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							:	str     , UpperCAmelCase							:	Matrix   )	->       int:
											if self.__width == other.width() and self.__height == other.height():
																	lowerCAmelCase   :Union[str, Any]						=			[]
																	for i in range(self.__height   ):
																							lowerCAmelCase   :List[Any]						=			[
																							    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							:	Optional[int]     , UpperCAmelCase							:	Matrix   )	->       Any:
											if self.__width == other.width() and self.__height == other.height():
																	lowerCAmelCase   :int						=			[]
																	for i in range(self.__height   ):
																							lowerCAmelCase   :List[str]						=			[
																							    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]     , UpperCAmelCase							:	float   )	->       int:
											...
					@overload
					def __mul__(							self							:	Optional[Any]     , UpperCAmelCase							:	Vector   )	->       Union[str, Any]:
											...
					def __mul__(							self							:	Tuple     , UpperCAmelCase							:	float | Vector   )	->       Optional[int]:
											if isinstance(__lowerCamelCase     , __lowerCamelCase   ):  # matrix-vector
																	if len(__lowerCamelCase   ) == self.__width:
																							lowerCAmelCase   :int						=			zero_vector(self.__height   )
																							for i in range(self.__height   ):
																													lowerCAmelCase   :Any						=			[
																													    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
																	lowerCAmelCase   :Any						=			[
																	    [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        UpperCAmelCase__ (							self							:	Any   )	->       Dict:
											return self.__height
					def        UpperCAmelCase__ (							self							:	Dict   )	->       Union[str, Any]:
											return self.__width
					def        UpperCAmelCase__ (							self							:	Any     , UpperCAmelCase							:	int     , UpperCAmelCase							:	int   )	->       Union[str, Any]:
											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        UpperCAmelCase__ (							self							:	Tuple     , UpperCAmelCase							:	int     , UpperCAmelCase							:	int     , UpperCAmelCase							:	float   )	->       List[Any]:
											if 0 <= x < self.__height and 0 <= y < self.__width:
																	lowerCAmelCase   :Union[str, Any]						=			value
											else:
																	raise Exception('change_component: indices out of bounds'   )
					def        UpperCAmelCase__ (							self							:	str     , UpperCAmelCase							:	int     , UpperCAmelCase							:	int   )	->       Dict:
											if self.__height != self.__width:
																	raise Exception('Matrix is not square'   )
											lowerCAmelCase   :Tuple						=			self.__matrix[:x] + self.__matrix[x + 1 :]
											for i in range(len(__lowerCamelCase   )   ):
																	lowerCAmelCase   :Tuple						=			minor[i][:y] + minor[i][y + 1 :]
											return Matrix(__lowerCamelCase     , self.__width - 1     , self.__height - 1   ).determinant()
					def        UpperCAmelCase__ (							self							:	Optional[int]     , UpperCAmelCase							:	int     , UpperCAmelCase							:	int   )	->       List[str]:
											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        UpperCAmelCase__ (							self							:	Optional[int]   )	->       List[Any]:
											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:
																	lowerCAmelCase   :Any						=			[
																	    self.__matrix[0][y] * self.cofactor(0     , __lowerCamelCase   ) for y in range(self.__width   )
																	]
																	return sum(__lowerCamelCase   )


def        UpperCAmelCase      (					a__ ):





						'''simple docstring'''






						lowerCAmelCase   :Any						=			[[0] * n for _ in range(lowerCAmelCase_ )]
						return Matrix(lowerCAmelCase_     ,      lowerCAmelCase_     ,      lowerCAmelCase_ )







def        UpperCAmelCase      (					a__     ,      a__     ,      a__     ,      a__ ):





						'''simple docstring'''






						random.seed(lowerCAmelCase_ )
						lowerCAmelCase   :Optional[int]						=			[
						    [random.randint(lowerCAmelCase_     ,      lowerCAmelCase_ ) for _ in range(lowerCAmelCase_ )] for _ in range(lowerCAmelCase_ )
						]
						return Matrix(lowerCAmelCase_     ,      lowerCAmelCase_     ,      lowerCAmelCase_ )




"""simple docstring"""






import operator




def 			snake_case		(		lowerCAmelCase_  ,						lowerCAmelCase_ = False  ,						lowerCAmelCase_ = None	)						->				list:
  _snake_case   	=      operator.lt if reverse else operator.gt
  _snake_case   	=      solution or []

  if not arr:
    return solution

  _snake_case   	=      [arr.pop(0	)]
  for i, item in enumerate(lowerCAmelCase_	):
    if _operator(lowerCAmelCase_  ,						sublist[-1]	):
      sublist.append(lowerCAmelCase_	)
      arr.pop(lowerCAmelCase_	)

    #  merging sublist into solution list
  if not solution:
    solution.extend(lowerCAmelCase_	)
  else:
    while sublist:
      _snake_case   	=      sublist.pop(0	)
      for i, xx in enumerate(lowerCAmelCase_	):
        if not _operator(lowerCAmelCase_  ,						lowerCAmelCase_	):
          solution.insert(lowerCAmelCase_  ,						lowerCAmelCase_	)
          break
      else:
        solution.append(lowerCAmelCase_	)

  strand_sort(lowerCAmelCase_  ,						lowerCAmelCase_  ,						lowerCAmelCase_	)
  return solution


if __name__ == "__main__":
     assert strand_sort([4, 3, 5, 1, 2]) == [1, 2, 3, 4, 5]
     assert strand_sort([4, 3, 5, 1, 2], reverse=True) == [5, 4, 3, 2, 1]





