Учительская сторона математики

Одна из задач, которую студенты регулярно выполняют на уроках математики, заключается в решении полиномиального уравнения. Это значит, что, имея полином, например, X^2 − 4X + 1, нужно найти его корни (2 ± ).

Если задача студентов — найти корни данного полинома, то задача учителя — найти полином, который имеет данный корень. Миссис Гальсоне — увлеченный учитель математики, которой наскучило находить решения квадратных уравнений, таких простых, как a + b. Она хотела составлять уравнения более высокой степени, решения которых немного сложнее. Как обычно в задачах на уроках математики, она хочет, чтобы все коэффициенты были целыми числами и степень полинома была как можно меньше (при условии, что он имеет заданный корень). Пожалуйста, помогите ей, написав программу, которая выполняет задачу со стороны учителя.

Вам дано число t в следующей форме:

t = +

где a и b — различные простые числа, а m и n — целые числа больше 1.

В этой задаче вам нужно найти минимальный полином на целых числах для t, который является полиномом

F(X) = a_dX^d + a_{d−1}X^{d−1} + · · · + a_1X + a_0

удовлетворяющим следующим условиям.

1. Коэффициенты a_0, ..., a_d являются целыми числами и a_d > 0.

2. F(t) = 0.

3. Степень d минимальна среди полиномов, удовлетворяющих двум предыдущим условиям.

4. F(X) является примитивным. То есть, коэффициенты a_0, ..., a_d не имеют общих делителей больше единицы.

Например, минимальный полином для + на целых числах — это F(X) = X^4−10X^2+1. Проверка, что F(t) = 0, так же проста, как и следующее (α = , β = ).

F(t) = (α + β)^4 − 10(α + β)^2 + 1

= (α^4 + 4α^3β + 6α^2β^2 + 4αβ^3 + β^4) − 10(α^2 + 2αβ + β^2) + 1

= 9 + 12αβ + 36 + 8αβ + 4 − 10(3 + 2αβ + 2) + 1

= (9 + 36 + 4 − 50 + 1) + (12 + 8 − 20)αβ = 0

Проверка, что степень F(t) действительно минимальна, немного сложнее. К счастью, при условии, заданном в этой задаче, что a и b — различные простые числа, а m и n больше единицы, степень минимального полинома всегда равна mn. Более того, он всегда монический. То есть коэффициент его старшего члена (a_d) равен единице.

Входные данные

Входные данные состоят из нескольких наборов данных, каждый из которых имеет следующий формат.

a m b n

Эта строка представляет m + n. Последний набор данных завершается строкой, состоящей из четырех нулей. Числа в одной строке разделены одним пробелом.

Каждый набор данных удовлетворяет следующим условиям.

1. m

   

   + n

   

   ≤ 4.

2. mn ≤ 20.

3. Коэффициенты ответа a_0, ..., a_d находятся в диапазоне от (−2^31 + 1) до (2^31 − 1), включительно.

Выходные данные

Для каждого набора данных выведите коэффициенты его минимального полинома на целых числах

F(X) = a_dX^d + a_{d−1}X^{d−1} + ··· + a_1X + a_0,

в следующем формате.

a_d a_{d−1} ... a_1 a_0

Неотрицательные числа должны быть напечатаны без знака (+ или −). Числа в одной строке должны быть разделены одним пробелом, и никакие другие символы или лишние пробелы не должны появляться в выводе.

Примеры