The Teacher's Side of Math

One of the tasks students routinely carry out in their mathematics classes is to solve a polynomial equation: given a polynomial, say $X^2 - 4X + 1$, find its roots $2 \pm \sqrt{3}$.

If the students' task is to find the roots of a given polynomial, the teacher's task is to find a polynomial that has a given root. Ms. Galsone is an enthusiastic mathematics teacher who is bored with finding solutions of quadratic equations as simple as $a + b\sqrt{c}$. She wants to make higher-degree equations whose solutions are a little more complicated. As usual in mathematics-class problems, she wants all coefficients to be integers and the degree of the polynomial to be as small as possible (provided it has the specified root). Please help her by writing a program that carries out the teacher's task.

You are given a number $t$ of the form

$t = \sqrt[m]{a} + \sqrt[n]{b}$

where $a$ and $b$ are distinct prime numbers and $m$ and $n$ are integers greater than $1$.

You are asked to find $t$'s minimal polynomial over the integers, which is the polynomial $F(X) = a_d X^d + a_{d-1} X^{d-1} + \cdots + a_1 X + a_0$ satisfying the following conditions.

1. The coefficients $a_0, \dots, a_d$ are integers and $a_d > 0$.
2. $F(t) = 0$.
3. The degree $d$ is the minimum among polynomials satisfying the above two conditions.
4. $F(X)$ is primitive; that is, the coefficients $a_0, \dots, a_d$ have no common divisor greater than one.

For example, the minimal polynomial of $\sqrt{3} + \sqrt{2}$ over the integers is $F(X) = X^4 - 10X^2 + 1$. Verifying $F(t) = 0$ is as simple as the following (let $\alpha = \sqrt{3}$, $\beta = \sqrt{2}$).

$F(t) = (\alpha + \beta)^4 - 10(\alpha + \beta)^2 + 1$

$= (\alpha^4 + 4\alpha^3\beta + 6\alpha^2\beta^2 + 4\alpha\beta^3 + \beta^4) - 10(\alpha^2 + 2\alpha\beta + \beta^2) + 1$

$= 9 + 12\alpha\beta + 36 + 8\alpha\beta + 4 - 10(3 + 2\alpha\beta + 2) + 1$

$= (9 + 36 + 4 - 50 + 1) + (12 + 8 - 20)\alpha\beta = 0$

Verifying that the degree of $F$ is in fact minimum is a bit more difficult. Fortunately, under the conditions given in this problem — $a$ and $b$ distinct primes and $m, n$ greater than one — the degree of the minimal polynomial is always $mn$. Moreover, it is always monic; that is, the coefficient of its highest-order term, $a_d$, is one.

The input consists of multiple datasets, each in the following format.

a m b n

This line represents $\sqrt[m]{a} + \sqrt[n]{b}$. The last dataset is followed by a single line consisting of four zeros. Numbers in a single line are separated by a single space.

Every dataset satisfies the following conditions.

1. $\sqrt[m]{a} + \sqrt[n]{b} \le 4$.
2. $mn \le 20$.
3. The coefficients of the answer $a_0, \dots, a_d$ are between $-231 + 1$ and $231 - 1$, inclusive.

The input consists of multiple datasets, each in the following format.

a m b n

This line represents $\sqrt[m]{a} + \sqrt[n]{b}$. The last dataset is followed by a single line consisting of four zeros. Numbers in a single line are separated by a single space.

Every dataset satisfies the following conditions.

1. $\sqrt[m]{a} + \sqrt[n]{b} \le 4$.
2. $mn \le 20$.
3. The coefficients of the answer $a_0, \dots, a_d$ are between $-231 + 1$ and $231 - 1$, inclusive.

For each dataset, output the coefficients of its minimal polynomial over the integers $F(X) = a_d X^d + a_{d-1} X^{d-1} + \cdots + a_1 X + a_0$, in the following format.

ad ad-1 ... a1 a0

Non-negative integers must be printed without a sign ($+$ or $-$). Numbers in a single line must be separated by a single space, and no other characters or extra spaces may appear in the output.