from fractions import Fraction

tests = ('1 2 0 0 7\n0 3 4 0 8\n0 0 5 6 9',
         '1 5/2 1/2 0 4 1/8\n0 5 2 -5/2 6 2',
         '1/20 -10/3 -10/9 -13\n-29 8 -27/4 0\n-26 -14 25 10/7',
         '1 1 2\n 2 1 -1\n1 -1 0',
         '0 0 1 2 1\n1 2 1 3 1\n1 2 2 5 2'
        )

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 solve(s):
    print(s)
    arr = [[Fraction(c) for c in r.split()] for r in s.split('\n')]
    num_vars = len(arr[0]) - 1
    
    # Remove redundant lines
    gauss_arr = [row for row in gauss(arr) if not all(x == 0 for x in row)]
    num_row = len(gauss_arr)
    for r in gauss_arr:
        print(r)

    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 = f"SOL=({'; '.join(['0'] * num_vars) + ')'} + {' + '.join(line(i) for i in range(num_vars))}"
        print(bool(re.match(re_sol, sol)))
        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:
        print("No solution")
        return "SOL=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])
    print("num_vars :", num_vars)
    print("others :", others)
    print("dependants :", dpts)
    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])
        # print("Begin _j:", _j, dpts[_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]

    
        # print("After cleaning, dependants :", dpts[_j])   

    for o in others:
        if o != num_vars:
            dpts[o] = {o: 1}
    print("Final :", dpts)
    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[:])
    ans = "SOL="+' + '.join([f"{'' if i == 0 else 'q' + str(i) + ' * ' }({'; '.join(str(x) for x in r)})" for i, r in enumerate(sol)])
    print(ans)
    return  ans
for test in tests:
    r = solve(test)
    print(r)


# for l in gauss_arr:
#     print(list(map(round, l)))
# def solve(a):
#     n, m = len(a), len(a[0])
#     arr = gauss(a)  
#     print(arr)
#     sol = [None] * n
#     sol[-1] = arr[-1][-1] / arr[-1][-2]
#     for i in range(n - 2, -1, -1):
#         sol[i] = (arr[i][-1] - sum(arr[i][j] * sol[j] for j in range(i + 1, n))) / arr[i][i]
#     return sol

# def gauss_solve(a, b):
#     arr = [r[:] for r in a]
#     for i in range(len(arr)):
#         arr[i].append(b[i])
#     sol = solve(arr)
#     return sol
    
# a = [[1, 1, 1, 0], [1, 1, 0, 1], [1, 0, 1, 1], [0, 1, 1, 1]]
# b = [1, -1, 2, 3]
# x = gauss_solve(a, b)
# print(x)