import random

def matrika(n):
    """Nova ničelna matrika velikosti n x n"""
    return [[0 for j in range(0,n)] for i in range(0,n)]


def dim(a):
    """Dimenzija kvadratne matrike a"""
    return len(a)


def vsota(a, b):
    """Vsota kvadratnih matrik."""
    assert (dim(a) == dim(b))
    n = dim(a)
    return [[a[i][j] + b[i][j] for j in range(0,n)] for i in range(0,n)]


def razlika(a, b):
    """Razlika kvadratnih matrik."""
    assert (dim(a) == dim(b))
    n = dim(a)
    return [[a[i][j] - b[i][j] for j in range(0,n)] for i in range(0,n)]


def dopolni(a):
    """Matriki dodaj spodaj vrstico in desno stolpec ničel."""
    n = dim(a)
    b = [v + [0] for v in a]
    b.append([0 for i in range(0,n+1)])
    return b


def nakljucna(n):
    """Naključna n x n matrika števil v razponu 0 do 1."""
    return [[random.uniform(0,1) for i in range(0,n)] for j in range(0,n)]


def produkt(a,b):
    """Naivni produkt kvadratnih matrik."""
    assert (dim(a) == dim(b))
    n = dim(a)
    return [[sum([a[i][k] * b[k][j] for k in range(0,n)]) 
                                    for j in range(0,n)]
                                    for i in range(0,n)]


def blok(a, i0, i1, j0, j1):
    """Blok (i0:i1, j0:j1) matrike a."""
    return [a[i][j0:j1] for i in range(i0,i1)]


def nastavi_blok(a, i0, i1, j0, j1, b):
    """V matriki a nastavi blok (i0:i1, j0:j1) na b."""
    for i in range(i0,i1):
        a[i][j0:j1] = b[i - i0]


def supnorm(a, b):
    """Absolutna vrednost največje razlike med istoležnimi elementi a in b."""
    assert (dim(a) == dim(b))
    n = dim(a)
    return max(abs(a[i][j] - b[i][j]) for i in range(0,n)
                                    for j in range(0,n))


def strassen(a, b, minsize=1):
    """Zmnoži kvadratni matriki s Strassenovim algoritmom.
       Parameter minsize pove, pri kateri velikosti matrike nehamo uporabljati
       Strassenovo množenje in preklopimo na navadno množenje.
    """
    assert (dim(a) == dim(b))
    n = dim(a)
    if n <= minsize:
        # Matrika je majhna, uporabimo navadno množenje
        return produkt(a,b)
    if n % 2 == 1:
        # liha velikost, dodamo eno vrstico in stolpec matrikama
        a = dopolni(a)
        b = dopolni(b)
    d = dim(a) // 2 # velikost bloka
    # Bločne podmatrike a
    a11 = blok(a, 0,   d, 0,   d)
    a12 = blok(a, 0,   d, d, 2*d)
    a21 = blok(a, d, 2*d, 0,   d)
    a22 = blok(a, d, 2*d, d, 2*d)
    # Bločne podmatrike b
    b11 = blok(b, 0,   d, 0,   d)
    b12 = blok(b, 0,   d, d, 2*d)
    b21 = blok(b, d, 2*d, 0,   d)
    b22 = blok(b, d, 2*d, d, 2*d)
    # Pomožne matrike m1, ..., m7
    m1 = strassen(vsota(a11, a22), vsota(b11, b22), minsize=minsize)
    m2 = strassen(vsota(a21, a22), b11, minsize=minsize)
    m3 = strassen(a11, razlika(b12, b22), minsize=minsize)
    m4 = strassen(a22, razlika(b21, b11), minsize=minsize)
    m5 = strassen(vsota(a11, a12), b22, minsize=minsize)
    m6 = strassen(razlika(a21, a11), vsota(b11, b12), minsize=minsize)
    m7 = strassen(razlika(a12, a22), vsota(b21, b22), minsize=minsize)
    # Sestavimo odgovor
    c = matrika(2*d)
    nastavi_blok(c, 0,  d,  0,   d, vsota(razlika(m4, m5), vsota(m1, m7)))
    nastavi_blok(c, 0,  d,  d, 2*d, vsota(m3, m5))
    nastavi_blok(c, d, 2*d, 0,   d, vsota(m2, m4))
    nastavi_blok(c, d, 2*d, d, 2*d, vsota(razlika(m1, m2), vsota(m3, m6)))
    # Obrežemo eno vrstico in stolpec, če je n lih
    if n % 2 == 1:
        return blok(c, 0, n, 0, n)
    else:
        return c