





'''simple docstring'''





from __future__ import annotations

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

class        _a    :






     def __init__(			self ,_SCREAMING_SNAKE_CASE = None   )							->      None:
          if components is None:
               _snake_case							=				[]
          _snake_case							=				list(_SCREAMING_SNAKE_CASE   )






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






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






     def __add__(			self ,_SCREAMING_SNAKE_CASE   )							->      Vector:
          _snake_case							=				len(self   )
          if size == len(_SCREAMING_SNAKE_CASE   ):
               _snake_case							=				[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 ,_SCREAMING_SNAKE_CASE   )							->      Vector:
          _snake_case							=				len(self   )
          if size == len(_SCREAMING_SNAKE_CASE   ):
               _snake_case							=				[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 ,_SCREAMING_SNAKE_CASE   )							->      Vector:
          ...






     @overload
     def __mul__(			self ,_SCREAMING_SNAKE_CASE   )							->      float:
          ...






     def __mul__(			self ,_SCREAMING_SNAKE_CASE   )							->      float | Vector:
          if isinstance(_SCREAMING_SNAKE_CASE ,(float, int)   ):
               _snake_case							=				[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   ):
               _snake_case							=				len(self   )
               _snake_case							=				[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     _lowercase     (			self   )							->      Vector:
          return Vector(self.__components   )






     def     _lowercase     (			self ,_SCREAMING_SNAKE_CASE   )							->      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     _lowercase     (			self ,_SCREAMING_SNAKE_CASE ,_SCREAMING_SNAKE_CASE   )							->      None:
          assert -len(self.__components   ) <= pos < len(self.__components   )
          _snake_case							=				value






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






     def     _lowercase     (			self ,_SCREAMING_SNAKE_CASE ,_SCREAMING_SNAKE_CASE = False   )							->      float:
          _snake_case							=				self * other
          _snake_case							=				self.euclidean_length() * other.euclidean_length()
          if deg:
               return math.degrees(math.acos(num / den   )   )
          else:
               return math.acos(num / den   )







def      __a     (       _UpperCamelCase:   int   )						->			Vector:

     """simple docstring"""




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





def      __a     (       _UpperCamelCase:   int ,						_UpperCamelCase:   int   )						->			Vector:

     """simple docstring"""




     assert isinstance(_UpperCamelCase ,						_UpperCamelCase   ) and (isinstance(_UpperCamelCase ,						_UpperCamelCase   ))
     _snake_case							=				[0] * dimension
     _snake_case							=				1
     return Vector(_UpperCamelCase   )





def      __a     (       _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      __a     (       _UpperCamelCase:   int ,						_UpperCamelCase:   int ,						_UpperCamelCase:   int   )						->			Vector:

     """simple docstring"""




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

class        _a    :






     def __init__(			self ,_SCREAMING_SNAKE_CASE ,_SCREAMING_SNAKE_CASE ,_SCREAMING_SNAKE_CASE   )							->      None:
          _snake_case							=				matrix
          _snake_case							=				w
          _snake_case							=				h






     def __str__(			self   )							->      str:
          _snake_case							=				""
          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 ,_SCREAMING_SNAKE_CASE   )							->      Matrix:
          if self.__width == other.width() and self.__height == other.height():
               _snake_case							=				[]
               for i in range(self.__height   ):
                    _snake_case							=				[
                        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 ,_SCREAMING_SNAKE_CASE   )							->      Matrix:
          if self.__width == other.width() and self.__height == other.height():
               _snake_case							=				[]
               for i in range(self.__height   ):
                    _snake_case							=				[
                        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 ,_SCREAMING_SNAKE_CASE   )							->      Matrix:
          ...






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






     def __mul__(			self ,_SCREAMING_SNAKE_CASE   )							->      Vector | Matrix:
          if isinstance(_SCREAMING_SNAKE_CASE ,_SCREAMING_SNAKE_CASE   ):  # matrix-vector
               if len(_SCREAMING_SNAKE_CASE   ) == self.__width:
                    _snake_case							=				zero_vector(self.__height   )
                    for i in range(self.__height   ):
                         _snake_case							=				[
                             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
               _snake_case							=				[
                   [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     _lowercase     (			self   )							->      int:
          return self.__height






     def     _lowercase     (			self   )							->      int:
          return self.__width






     def     _lowercase     (			self ,_SCREAMING_SNAKE_CASE ,_SCREAMING_SNAKE_CASE   )							->      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     _lowercase     (			self ,_SCREAMING_SNAKE_CASE ,_SCREAMING_SNAKE_CASE ,_SCREAMING_SNAKE_CASE   )							->      None:
          if 0 <= x < self.__height and 0 <= y < self.__width:
               _snake_case							=				value
          else:
               raise Exception("change_component: indices out of bounds"   )






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






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







def      __a     (       _UpperCamelCase:   int   )						->			Matrix:

     """simple docstring"""




     _snake_case							=				[[0] * n for _ in range(_UpperCamelCase   )]
     return Matrix(_UpperCamelCase ,						_UpperCamelCase ,						_UpperCamelCase   )





def      __a     (       _UpperCamelCase:   int ,						_UpperCamelCase:   int ,						_UpperCamelCase:   int ,						_UpperCamelCase:   int   )						->			Matrix:

     """simple docstring"""




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








'''simple docstring'''





from __future__ import annotations

from typing import Any





def      __a     (       _UpperCamelCase:   list[Any]   )						->			None:

     """simple docstring"""




     create_state_space_tree(_UpperCamelCase ,						[] ,						0   )





def      __a     (       _UpperCamelCase:   list[Any] ,						_UpperCamelCase:   list[Any] ,						_UpperCamelCase:   int   )						->			None:

     """simple docstring"""




     if index == len(_UpperCamelCase   ):
          print(_UpperCamelCase   )
          return

     create_state_space_tree(_UpperCamelCase ,						_UpperCamelCase ,						index + 1   )
     current_subsequence.append(sequence[index]   )
     create_state_space_tree(_UpperCamelCase ,						_UpperCamelCase ,						index + 1   )
     current_subsequence.pop()


if __name__ == "__main__":
   UpperCamelCase_						:      list[Any]       =						[3, 1, 2, 4]
   generate_all_subsequences(seq)

   seq.clear()
   seq.extend(['''A''', '''B''', '''C'''])
   generate_all_subsequences(seq)


