from fractions import Fraction
P = [[0, 3, 3], [0, 3, 1], [1, 3, 1]]
mod = 4
# 1, 1, 0, -1, -1, 0, ...
def seq(n):
    return [1, 1, 0, -1, -1, 0][n % 6]
   
def show(m):
    return "\n".join(" ".join(map(str, r)) for r in m) + "\n"
    
# move(P, 0, 1, 1, mod)
# print(show(P))
# move(P, 0, 2, 3, mod)
# print(show(P))
# ##########
# move(P, 1, 1, 3, mod)
# print(show(P))
# move(P, 1, 2, 2, mod)
# print(show(P))
# ###########
# move(P, 2, 0, 2, mod)
# print(show(P))
# move(P, 2, 1, 2, mod)
# print(show(P))

class Dict:
    def __init__(self, d):
        self.d = d

    def __add__(self, other):
        d = {}
        for k in set(self.d.keys()) | set(other.d.keys()):
            d[k] = self.d.get(k, 0) + other.d.get(k, 0)
        return Dict(d)

    def __sub__(self, other):
        d = {}
        for k in set(self.d.keys()) | set(other.d.keys()):
            d[k] = self.d.get(k, 0) - other.d.get(k, 0)
        return Dict(d)
        
    def __neg__(self):
        return Dict({k: -v for k, v in self.d.items()})

    def __rmul__(self, c):
        assert type(c) == int, "Multiplication impossible"
        return Dict({k: c * v for k, v in self.d.items()})

    def __mul__(self, c):
        assert type(c) == int, "Multiplication impossible"
        return Dict({k: c * v for k, v in self.d.items()})

    def __repr__(self):
        return f"{{{', '.join('{}: {}'.format(k, v) for k, v in self.d.items())}}}"

def get_next_row(m, row):
    m = len(row)
    if m % 3 == 2:
        return get_next_row(m - 1, row[:-1]) + [0]
    inv = (
        lambda i, j: (-1 if (i + j) % 2 else 1)
        * (seq(min(i + 1, j + 1) - 1) * seq(m - max(i + 1, j + 1)))
        // seq(m)
    )
    res = []
    for i in range(m):
        r = Dict({})
        for j in range(m):
            r -= inv(i, j) * row[j]
        res.append(r)
    return res

def move(B, x, y, add):
    n, m = len(B), len(B[0])
    for dx in (-1, 0, 1):
        for dy in (-1, 0, 1):
            u, v = x + dx, y + dy
            if 0 <= u < n and 0 <= v < m:
                B[u][v] = B[u][v] + add


def gauss(arr):
    n, m = len(arr), len(arr[0])
    h, k = 0, 0
    while h < n and k < m:
        idx = next((i for i in range(h, n) if arr[i][k] != 0), None)
        if idx is None:
            k += 1
        else:
            arr[idx], arr[h] = arr[h], arr[idx]
            for i in range(h + 1, n):
                f = arr[i][k] / arr[h][k]
                arr[i][k] = Fraction(0)
                for j in range(k + 1, m):
                    arr[i][j] -= arr[h][j] * f
            h += 1
            k += 1
    return arr

def gauss_solve(A, B, mod):

    n = len(A)
    arr = [[Fraction(x) for x in A[i]] + [B[i]] for i in range(n)]
    num_vars = len(arr[0]) - 1
    
    # Remove redundant lines
    gauss_arr = [row for row in gauss(arr) if not all(x % mod == 0 for x in row)]
#     print("gauss_arr")
#     for r in gauss_arr:
#         print([int(x) for x in r])
    num_row = len(gauss_arr)

    if len(gauss_arr) == 0:
        line=lambda i:f"q{i + 1} * ({'; '.join(['1' if j == i else '0' for j in range(num_vars)])})"
        sol = ['0'] * num_vars
        return sol

        
    idx = next((j for j in range(num_vars) if gauss_arr[-1][j] != 0), None)
    if idx is None and gauss_arr[-1][-1] != 0:
        return None

    others = set(range(idx + 1, num_vars + 1)) 
    # Last line
    dpts = {idx: {}}
    dpts[idx][num_vars] = gauss_arr[-1][num_vars] / gauss_arr[-1][idx]
    for j in range(idx + 1, num_vars):
        if gauss_arr[-1][j] != 0:
            dpts[idx] [j] = -(gauss_arr[-1][j] / gauss_arr[-1][idx])
    for i in range(num_row - 2, -1, -1):
        _j = next((j for j in range(num_vars) if gauss_arr[i][j] != 0), None)
        
        dpts[_j] = {num_vars: gauss_arr[i][num_vars] / gauss_arr[i][_j]}
        
        for k in range(_j + 1, num_vars):
            if gauss_arr[i][k] != 0:
                dpts[_j][k] = -(gauss_arr[i][k] / gauss_arr[i][_j])

        others |= set([k for k in range(_j + 1, min(others)) if not k in dpts])
        while any(not k in others and k != num_vars for k in dpts[_j]):
            k = next(_k for _k in dpts[_j] if not _k in sorted(others) and k != num_vars)
            for key, value in dpts[k].items():
                dpts[_j][key] = dpts[_j].get(key, 0) + dpts[_j][k] * value
            # Remove value from dict
            del dpts[_j][k]

    for o in others:
        if o != num_vars:
            dpts[o] = {o: 1}
    sol = []
    for i in sorted(others, reverse=True):
        r = []
        for key in sorted(dpts.keys()):
            r.append(dpts[key].get(i, 0))
        sol.append(r[:])
    return sol[0]

    



def solve(A, mod):
    n, m = len(A), len(A[0])
    arr = [[Dict({'c': A[i][j]}) for j in range(m)] for i in range(n)]
    for i in range(2):
        for j in range(1, m - 1):
            arr[i][j] += Dict({j - 1: 1, j: 1, j + 1: 1})
        arr[i][0] += Dict({0: 1, 1: 1})
        arr[i][m - 1] += Dict({m - 2: 1, m - 1: 1})

    seq = [[Dict({i: 1}) for i in range(m)]]
    for i in range(n - 1):
        s = get_next_row(m, arr[i])
        seq.append(s)
        for j, c in enumerate(s):
            move(arr, i + 1, j, c)
    mat = []
    b = []
    for s in arr[-1]:
        r = []
        for j in range(m):
            r.append(s.d.get(j, 0))
        b.append(-s.d.get('c', 0))
        mat.append(r)
    gs = [int(x) % mod for x in gauss_solve(mat, b, mod)]
    print("seq")
    print(seq)
    ans = []
    res = []
    for i, ele in enumerate(seq):
        row = []
        for j, dct in enumerate(ele):
            _sum = 0
            for key, val in dct.d.items():
                _sum += gs[key] * val if key != 'c' else val
            sum_mod = _sum % mod
            row.append(sum_mod)
            if sum_mod != 0:
                res.append((i, j, sum_mod))
        ans.append(row)
    print(ans)
    print(res)
    return (seq, arr[-1])
    
r, s = solve(P, mod)
for d in r:
    print(d)
print("system")
print(s)