#!/usr/bin/env python3

from fractions import Fraction


OUTPUT = [
    [295662573273290623900407320667244440561913074, 398969263312250142846591713944233406242755402, 348748750178596858287457463436167770367743486, 1364037545534325541882463501082729953690961051],
    [575026186132965057911584617811112536209642264, 475019143092003929835430859115351077234156392, 306730089063421029803201145877510554629647601, 506049720455827979279301584495901051137471499],
    [84266604156989810704049456000281640732504848, 489861776717561426112183190426399395504819586, 343168692956493452627232161939238347545174591, 1300450584581165319714233483811149638923359733],
    [247265750644178124958450035605722570774151739, 316655879927503657733383936311500619683899343, 1294831694146552023902991223917286568358963480, 1191862843017346876917142321386548275775314968],
]


def magic(square: list[list[int]]) -> list[list[int]]:
    magic_square = [row[:] for row in square]

    for i in range(4):
        magic_square[0][i] += square[1][i]
        magic_square[1][i] += square[0][i]
        magic_square[2][i] += square[3][i]
        magic_square[3][i] += square[2][i]

    magic_square[0][0] += square[3][0] + square[0][1]
    magic_square[0][1] += square[0][0] + square[0][2]
    magic_square[0][2] += square[0][1] + square[0][3]
    magic_square[0][3] += square[0][2] + square[3][3]

    magic_square[1][0] += square[1][1] + square[1][3] + square[2][2]
    magic_square[1][1] += square[1][0] + square[2][3] + square[2][1]
    magic_square[1][2] += square[2][0] + square[2][2]
    magic_square[1][3] += square[1][0] + square[2][1]

    magic_square[2][0] += square[1][2] + square[2][3]
    magic_square[2][1] += square[1][1] + square[1][3]
    magic_square[2][2] += square[1][0] + square[1][2] + square[2][3]
    magic_square[2][3] += square[1][1] + square[2][0] + square[2][2]

    magic_square[3][0] += square[0][0] + square[3][1]
    magic_square[3][1] += square[3][0] + square[3][2]
    magic_square[3][2] += square[3][1] + square[3][3]
    magic_square[3][3] += square[3][2] + square[0][3]

    return magic_square


def build_matrix() -> list[list[Fraction]]:
    columns = []
    for index in range(16):
        square = [[0] * 4 for _ in range(4)]
        square[index // 4][index % 4] = 1
        transformed = magic(square)
        columns.append([Fraction(value) for row in transformed for value in row])
    return [list(row) for row in zip(*columns)]


def solve_linear_system(matrix: list[list[Fraction]], vector: list[Fraction]) -> list[Fraction]:
    augmented = [row[:] + [value] for row, value in zip(matrix, vector)]
    size = len(augmented)
    pivot_cols = []
    pivot_row = 0

    for col in range(size):
        swap_row = None
        for row in range(pivot_row, size):
            if augmented[row][col] != 0:
                swap_row = row
                break
        if swap_row is None:
            continue

        augmented[pivot_row], augmented[swap_row] = augmented[swap_row], augmented[pivot_row]
        pivot = augmented[pivot_row][col]
        augmented[pivot_row] = [value / pivot for value in augmented[pivot_row]]

        for row in range(size):
            if row == pivot_row or augmented[row][col] == 0:
                continue
            factor = augmented[row][col]
            augmented[row] = [
                augmented[row][idx] - factor * augmented[pivot_row][idx]
                for idx in range(size + 1)
            ]

        pivot_cols.append(col)
        pivot_row += 1

    solution = [Fraction(0) for _ in range(size)]
    for row, col in enumerate(pivot_cols):
        solution[col] = augmented[row][-1]
    return solution


def decode_integer(value: int) -> str:
    hex_value = f"{value:x}"
    if len(hex_value) % 2:
        hex_value = "0" + hex_value
    return bytes.fromhex(hex_value).decode("ascii")


def main() -> None:
    matrix = build_matrix()
    vector = [Fraction(value) for row in OUTPUT for value in row]
    solution = solve_linear_system(matrix, vector)

    flag_number = sum(solution)
    if flag_number.denominator != 1:
        raise ValueError("flag is not an integer")

    flag = decode_integer(int(flag_number))
    print(flag)


if __name__ == "__main__":
    main()