from gmpy2 import gcd, invert, powmod
with open('output.txt', 'r') as f:
    code = f.read()
    exec(code)
'''
(hints[0] = a1 * p + b1 * q) * a2 (1)
(hints[1] = a2 * p + b2 * q) * a1 (2)
(1) - (2):
hints[0] * a2 - hints[1] * a1 =
b1 * a2 * q - b2 * a1 * q = (b1 * a2 - b2 * a1) * q
because q is a prime, n = p * q, gcd((1) - (2), n) = q
'''
for a1 in range(0, 2**12):
    for a2 in range(0, 2**12):
        q = gcd(abs(hints[0] * a2 - hints[1] * a1), n)
        if q == 1 or q == n:
            continue
        p = n // q
        print(p)
        print(q)
        mod = (p-1) * (q-1)
        e = 0x10001
        d = invert(e, mod)
        m = powmod(c, d, n)
        from Cryptodome.Util.number import long_to_bytes
        print(long_to_bytes(m))