from collections import defaultdict

# 1, 1, 0, -1, -1, 0, ...
def seq(n):
    return [1, 1, 0, -1, -1, 0][n % 6]


def get_next_row(n, row, mod):
    if n % 3 == 2:
        return get_next_row(n - 1, row[:-1], mod) + [0]
    inv = (
        lambda i, j: (-1 if (i + j) % 2 else 1)
        * (seq(min(i + 1, j + 1) - 1) * seq(n - max(i + 1, j + 1)))
        // seq(n)
    )
    res = [(sum(inv(i, j) * (-row[j]) for j in range(n))) % mod for i in range(n)]
    return res

def show(m):
    return "\n".join(" ".join(map(str, r)) for r in m) + "\n"


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) % mod


def solve(puzzle, mod):
    dct = defaultdict(int)
    print("Start")
    n, m = len(puzzle), len(puzzle[0])
    A = [r[:] for r in puzzle]
    for i in range(n - 1):
        if all(x == 0 for x in A[i]):
            continue
        seq = get_next_row(m, A[i], mod)
        for j, c in enumerate(seq):
            move(A, i + 1, j, c)
            dct[(i + 1, j)] += 1
        print("i:", i)
        print(show(A))

    print("Second step ")
    pre_moves = A[-1]
    print(pre_moves)
    s = get_next_row(m, pre_moves, mod)
    for j, v in enumerate(s):
        if v != 0:
            move(puzzle, 0, j, v)
    print(show(puzzle))
    for i in range(n - 1):
        if all(x == 0 for x in puzzle[i]):
            continue
        seq = get_next_row(m, puzzle[i], mod)
        print("seq :", seq)
        for j, c in enumerate(seq):
            move(puzzle, i + 1, j, c)
            dct[(i + 1, j)] += 1
        print("i:", i)
        print(show(puzzle))
    return [(k[0], k[1], v) for k, v in dct.items()]


P = [[0, 3, 3], [0, 3, 1], [1, 3, 1]]
mod = 4

ans = solve(P, mod)
print(ans)