import math


class Matrix:
    """
    Represents a mathematical matrix or vector.
    
    It is possible to fill this with anything one can multiply or add, even more matrices.
    """
    width = 0
    height = 0
    entries = []
    
    def multiply(self, other):  # Explicit multiply
        """Explicit version of the multiply operator."""
        if type(other) == int or type(other) == float: # By number
            out = [[0] * self.height for i in range(self.width)]
            for y in range(0, self.height):
                for x in range(0, self.width):
                    out[x][y] = self.entries[x][y] * other
            return self.__matrix_implicit(self.width, self.height, out)
        elif other.width == 1: # By vector
            if other.height != self.width:
                raise Exception("Illegal matrix-vector multiplication: other vector size ({}) "
                                "must match this matrix width ({})".format(other.height, self.width))
            out = [[0] * self.width]
            for y in range(0, self.height):
                for x in range(0, self.width):
                    out[0][y] += self.entries[x][y] * other.entries[0][x]
            return self.__matrix_implicit(1, self.height, out)
        else: # By matrix
            if other.height != self.width:
                raise Exception("Illegal matrix multiplication: other matrix height ({}) "
                                "must match this matrix width ({})".format(other.height, self.width))
            out = [[0] * self.height for i in range(other.width)]
            for leftX in range(self.width):
                for leftY in range(self.height):
                    for col in range(other.width):
                        out[col][leftY] += self.entries[leftX][leftY] * other.entries[col][leftX]
            return self.__matrix_implicit(other.width, self.height, out)
    
    def __mul__(self, other):  # Implicit multiply
        return self.multiply(other)
    
    def add(self, other):
        """Explicit version of the add operator."""
        if type(other) != Matrix: # Add non-matrix
            new = matrix_copy(self)
            for y in range(0, self.height):
                for x in range(0, self.width):
                    new.entries[x][y] += other
            return new
        else: # Add matrix
            if other.width != self.width or other.height != self.height:
                raise Exception("Illegal matrix addition: other matrix ({}, {}) must be the same size as "
                                "this matrix ({}, {})".format(other.width, other.height, self.width, self.height))
            new = matrix_copy(self)
            for y in range(0, self.height):
                for x in range(0, self.width):
                    new.entries[x][y] += other.entries[x][y]
            return new
    
    def __add__(self, other):
        return self.add(other)
    
    def __str__(self):
        maxW = 0
        for x in range(0, self.width):
            for y in range(0, self.height):
                w = len(str(self.entries[x][y]))
                if w > maxW:
                    maxW = w
        ret = ""
        for y in range(0, self.height):
            ret += "[ "
            for x in range(0, self.width):
                stuff = str(self.entries[x][y])
                ret += stuff + " " * (maxW + 1 - len(stuff))
            ret += "]\r\n"
        return ret
    
    def __matrix_implicit(self, width: int, height: int, entries: list): # Implicit constructor
        """Makes a matrix directly from its components, does not copy entries."""
        mtx = Matrix()
        mtx.width = width
        mtx.height = height
        mtx.entries = entries
        return mtx


def vector(*content):
    """Makes a vector with the given contents."""
    self = Matrix()
    self.width = 1
    self.height = len(content)
    self.entries = [[0] * self.height]
    for i in range(0, len(content)):
        self.entries[0][i] = content[i]
    return self


def vector_empty(size):
    """Makes an empty vector of the given size."""
    self = Matrix()
    self.width = 1
    self.height = size
    self.entries = [[0] * self.height]
    return self


def matrix_empty(width, height):
    """Makes an empty matrix of the given size."""
    self = Matrix()
    self.width = width
    self.height = height
    self.entries = [[0] * self.height for i in range(self.width)]
    return self


def matrix_copy(other):  # Copy constructor
    """Makes a copy of a matrix."""
    self = Matrix()
    self.width = other.width
    self.height = other.height
    self.entries = [[0] * self.height for i in range(self.width)]
    for y in range(0, self.height):
        for x in range(0, self.width):
            self.entries[x][y] = other.entries[x][y]
    return self


def matrix_identity(size: int):  # Identity "constructor"
    """Makes an identity matrix of given dimensions."""
    mtx = Matrix()
    mtx.width = size
    mtx.height = size
    mtx.entries = [[0] * size for i in range(size)]  # Create array
    for i in range(0, size):
        mtx.entries[i][i] = 1  # Add identity
    return mtx


def matrix_implicit(width, height, entries):
    """Makes making a matrix alot easier."""
    self = matrix_empty(width, height)
    for y in range(0, height):
        for x in range(0, width):
            self.entries[x][y] = entries[y * width + x]
    return self


def matrix_rotate_2D(angle):
    """Makes a matrix representing a 2D rotation."""
    return matrix_implicit(3, 3, [
        math.cos(angle), -math.sin(angle), 0,
        math.sin(angle), math.cos(angle), 0,
        0, 0, 1
    ])


def matrix_translate_2D(x, y):
    """Makes a matrix representing a 2D move."""
    return matrix_implicit(3, 3, [
        1, 0, x,
        0, 1, y,
        0, 0, 1
    ])


def matrix_scale_uniform_2D(factor):
    """Makes a matrix representing a uniform 2D scaling."""
    return matrix_implicit(3, 3, [
        factor, 0, 0,
        0, factor, 0,
        0, 0, 1
    ])


def matrix_scale_2D(scaleX, scaleY):
    """Makes a matrix representing a 2D scaling."""
    return matrix_implicit(3, 3, [
        scaleY, 0, 0,
        0, scaleX, 0,
        0, 0, 1
    ])


class MatrixStack2D:
    """Matrix stack which can represent simple 2D transformations such as scaling, rotating and moving."""
    matrices = []
    currentMatrix = None
    
    def __init__(self):
        self.clear() # Not really much more to do
    
    def multiplyMatrix(self, value):
        """
        Multiplies by a given input matrix.
        
        The input must be either 3 by 3 or 2 rows by 3 columns.
        
        If the input if 2x3, it will be converted internally.
        """
        if value.height == 2:
            value = matrix_implicit(3, 3, [
                value.entries[0][0], value.entries[1][0], value.entries[2][0],
                value.entries[0][1], value.entries[1][1], value.entries[2][1],
                0, 0, 1
            ])
        self.currentMatrix *= value
    
    def clear(self):
        self.currentMatrix = matrix_identity(3) # Identity matrix
        self.matrices = []  # Empty stack
    
    def push(self):
        """Pushes the current matrix onto the stack, thereby preserving it for later use."""
        self.matrices.append(matrix_copy(self.currentMatrix))
    
    def pop(self):
        """Pops a matrix off of the matrix stack and sets the current matrix."""
        if len(self.matrices) == 0:
            raise Exception("Matrix stack is already empty!")
        self.currentMatrix = matrix_copy(self.matrices[len(self.matrices) - 1])
        self.matrices.pop()
    
    def transformPoint(self, x, y):
        """Transforms the given point by the current transformation."""
        point = self.currentMatrix * vector(x, y, 1)
        return point.entries[0][0], point.entries[0][1]

    def translate(self, x, y):
        """Applies a transformation equivalent to moving relatively by X, Y."""
        self.currentMatrix *= matrix_translate_2D(x, y)

    def rotate2D(self, angleRadians):
        """Applies a transformation equivalent to rotating the entire canvas in 2D."""
        self.currentMatrix *= matrix_rotate_2D(angleRadians)

    def scale2D(self, scaleX, scaleY):
        """Applies a transformation equivalent to scaling X and Y in 2D."""
        self.currentMatrix *= matrix_scale_2D(scaleX, scaleY)