tests = [
    [[
    [1, 0, 1],
    [0, 0, 0],
    [1, 0, 1]
],[(1, 1)]],
    [[
    [0, 1, 0],
    [1, 0, 0],
    [0, 0, 1]
],[(0, 0), (1, 1)]],
    [[[1, 0, 1, 1, 1],
        [1, 0, 0, 0, 1],
        [1, 0, 0, 0, 1],
        [0, 0, 0, 0, 0],
        [1, 0, 1, 1, 1]],[(1, 3), (2, 1), (2, 2), (3, 1), (3, 2)]]
]


import numpy as np

def gauss_mod(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] = 0
                for j in range(k + 1, m):
                    arr[i][j] = (arr[i][j] - arr[h][j] * f) % 2
            h += 1
            k += 1

def make(arr, n):
    ans = [[0] for _ in range(n**2)]
    for y, x in arr:
        ans[n * x + y][0] = 1
    return ans

t = make ([(1, 3), (2, 1), (2, 2), (3, 1), (3, 2)], 5)
# print('t :', t)
def solve(arr):
    n = len(arr)
    x0 = []
    for i in range(n):
        for j in range(n):
            x0.append([arr[i][j]])
    # print(x0)
    arr = [[0 for _ in range(n**2)] for _ in range(n**2)]
    for k in range(n**2):
        i, j = divmod(k, n)
        for l in range(n):
            arr[n * i + l][k] = arr[n * l + j][k] = 1

    for i in range(n**2):
        arr[i].append(1 - x0[i][0])
   
    gauss_mod(arr)

    i = n**2 - 1
    while i >= 0 and all(x == 0 for x in arr[i]):
        i -= 1
    print("i :", i)
    arr = arr[:i+1]
    
    print("Gauss reduction :")
    for x in arr:
        print(x, ',') 
    cpy = [r[:] for r in arr]
    goods, frees = set([n**2]), set()
    for i in range(len(arr) - 1, -1, -1):
        idx = next(j for j in range(n**2) if arr[i][j] != 0)
        goods.add(idx)
        for j in range(idx, n**2):
            if arr[i][j] == 1 and not j in goods:
                frees.add(j)
    print(goods)
    print(frees)
    print("Length :", len(arr))
    sol = [0 for i in range(n**2)]
    for i in range(len(arr) - 1, -1, -1):
        idx = next(j for j in range(n**2) if arr[i][j] != 0)
        sol[idx] = (sum(arr[i][j] * sol[j] for j in range(idx + 1, n**2) if j in goods) + arr[i][n**2]) % 2
    print("sol :", sol)
    ans = []
    for k, v in enumerate(sol):
        if v != 0:
            ans.append((k % n, k //n))
    print("ans :", ans)


            
t0 = [[1, 0, 1, 1, 1],
        [1, 0, 0, 0, 1],
        [1, 0, 0, 0, 1],
        [0, 0, 0, 0, 0],
        [1, 0, 1, 1, 1]]
solve(t0)