def poly_print(f):
    n, f_c = f
    n = len(f_c) - 1
    poly_str = ""
    for i in range(len(f_c)):
        cur_cf = f_c[i]
        if not cur_cf:
            continue
        if cur_cf > 0:
            sign = "+"
        else:
            cur_cf = -cur_cf
            sign = "-"
        poly_str += f"{sign} {cur_cf}x^{n - i} "
    poly_str = poly_str[:len(poly_str) - 4]
    if poly_str[0] == "+":
        poly_str = poly_str[2:]
    return poly_str


def poly_reduction(f):
    n, f_c = f
    i = 0
    while i < len(f_c) and f_c[i] == 0:
        n -= 1
        i += 1
    return n, f_c[i:]


def inverse(n, field):
    x = 0
    for _ in range(field):
        if (n * x) % field != 1:
            x += 1
        else:
            break
    return x


def pdf(f, g, field):
    m, f_c = f
    n, g_c = g
    f_c.reverse()
    g_c.reverse()

    q_c = [0] * (m + 1)
    r_c = f_c

    for k in range(m - n, -1, -1):
        q_c[k] = (f_c[n + k] * inverse(g_c[n], field)) % field
        for j in range(n + k - 1, k - 1, -1):
            r_c[j] = (r_c[j] - q_c[k] * g_c[j - k]) % field

    q_c.reverse()
    r_c.reverse()

    return (m, q_c), (n, r_c)


if __name__ == "__main__":
    print("Введите коэффициенты первого многочлена:")
    cf = list(map(int, input().split()))
    f = poly_reduction((len(cf) - 1, cf))

    print("Введите коэффициенты второго многочлена:")
    cf = list(map(int, input().split()))
    g = poly_reduction((len(cf) - 1, cf))

    f_size = int(input("Введите размерность поля: "))

    q, r = pdf(f, g, f_size)

    print("Результат деления:", poly_print(q))
    if r is not None:
        print("Остаток от деления:", poly_print(r))
    else:
        print("Остатка нет")