




from __future__ import annotations

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





class 					__lowerCamelCase			:




    """simple docstring"""

    def __init__(			self	:	int  ,      SCREAMING_SNAKE_CASE__	:	Collection[float] | None = None  ) ->			None:
         if components is None:
              lowerCAmelCase__            =					[]
         lowerCAmelCase__            =					list(SCREAMING_SNAKE_CASE__  )


    def __len__(			self	:	Tuple  ) ->			int:
         return len(self.__components  )


    def __str__(			self	:	List[Any]  ) ->			str:
         return "(" + ",".join(map(SCREAMING_SNAKE_CASE__  ,      self.__components  )  ) + ")"


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


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


    @overload
    def __mul__(			self	:	List[str]  ,      SCREAMING_SNAKE_CASE__	:	float  ) ->			Vector:
         ...


    @overload
    def __mul__(			self	:	Dict  ,      SCREAMING_SNAKE_CASE__	:	Vector  ) ->			float:
         ...


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


    def   a (			self	:	Optional[int]  ) ->			Vector:
         return Vector(self.__components  )


    def   a (			self	:	Union[str, Any]  ,      SCREAMING_SNAKE_CASE__	:	int  ) ->			float:
         if isinstance(SCREAMING_SNAKE_CASE__  ,      SCREAMING_SNAKE_CASE__  ) and -len(self.__components  ) <= i < len(self.__components  ):
              return self.__components[i]
         else:
              raise Exception("index out of range"  )


    def   a (			self	:	str  ,      SCREAMING_SNAKE_CASE__	:	int  ,      SCREAMING_SNAKE_CASE__	:	float  ) ->			None:
         assert -len(self.__components  ) <= pos < len(self.__components  )
         lowerCAmelCase__            =					value


    def   a (			self	:	Tuple  ) ->			float:
         if len(self.__components  ) == 0:
              raise Exception("Vector is empty"  )
         lowerCAmelCase__            =					[c**2 for c in self.__components]
         return math.sqrt(sum(SCREAMING_SNAKE_CASE__  )  )


    def   a (			self	:	Dict  ,      SCREAMING_SNAKE_CASE__	:	Vector  ,      SCREAMING_SNAKE_CASE__	:	bool = False  ) ->			float:
         lowerCAmelCase__            =					self * other
         lowerCAmelCase__            =					self.euclidean_length() * other.euclidean_length()
         if deg:
              return math.degrees(math.acos(num / den  )  )
         else:
              return math.acos(num / den  )






def 				_A  (		lowerCAmelCase_	:   int     ):
     """simple docstring"""

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



def 				_A  (		lowerCAmelCase_	:   int  ,							lowerCAmelCase_	:   int     ):
     """simple docstring"""

     assert isinstance(lowerCAmelCase_  ,							lowerCAmelCase_     ) and (isinstance(lowerCAmelCase_  ,							lowerCAmelCase_     ))
     lowerCAmelCase__            =					[0] * dimension
     lowerCAmelCase__            =					1
     return Vector(lowerCAmelCase_     )



def 				_A  (		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 				_A  (		lowerCAmelCase_	:   int  ,							lowerCAmelCase_	:   int  ,							lowerCAmelCase_	:   int     ):
     """simple docstring"""

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





class 					__lowerCamelCase			:




    """simple docstring"""

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


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


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


    @overload
    def __mul__(			self	:	Optional[int]  ,      SCREAMING_SNAKE_CASE__	:	float  ) ->			Matrix:
         ...


    @overload
    def __mul__(			self	:	Tuple  ,      SCREAMING_SNAKE_CASE__	:	Vector  ) ->			Vector:
         ...


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


    def   a (			self	:	Dict  ) ->			int:
         return self.__height


    def   a (			self	:	Dict  ) ->			int:
         return self.__width


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


    def   a (			self	:	Union[str, Any]  ,      SCREAMING_SNAKE_CASE__	:	int  ,      SCREAMING_SNAKE_CASE__	:	int  ) ->			float:
         if self.__height != self.__width:
              raise Exception("Matrix is not square"  )
         lowerCAmelCase__            =					self.__matrix[:x] + self.__matrix[x + 1 :]
         for i in range(len(SCREAMING_SNAKE_CASE__  )  ):
              lowerCAmelCase__            =					minor[i][:y] + minor[i][y + 1 :]
         return Matrix(SCREAMING_SNAKE_CASE__  ,      self.__width - 1  ,      self.__height - 1  ).determinant()


    def   a (			self	:	List[Any]  ,      SCREAMING_SNAKE_CASE__	:	int  ,      SCREAMING_SNAKE_CASE__	:	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(SCREAMING_SNAKE_CASE__  ,      SCREAMING_SNAKE_CASE__  )
         else:
              raise Exception("Indices out of bounds"  )


    def   a (			self	:	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:
              lowerCAmelCase__            =					[
                  self.__matrix[0][y] * self.cofactor(0  ,      SCREAMING_SNAKE_CASE__  ) for y in range(self.__width  )
              ]
              return sum(SCREAMING_SNAKE_CASE__  )






def 				_A  (		lowerCAmelCase_	:   int     ):
     """simple docstring"""

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






def 				_A  (		lowerCAmelCase_	:   int  ,							lowerCAmelCase_	:   int  ,							lowerCAmelCase_	:   int  ,							lowerCAmelCase_	:   int     ):
     """simple docstring"""

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





a_      :      str    =     6_55_21






def     __a					(		__UpperCAmelCase       ):
 a__												= 1
 a__												= 0
 for plain_chr in plain_text:
  a__												= (a + ord(__UpperCAmelCase       )) % MOD_ADLER
  a__												= (b + a) % MOD_ADLER
 return (b << 16) | a





