原题面

题目描述(题面由AI千问翻译)

学生在数学课上经常执行的一项任务是求解多项式方程。也就是说，给定一个多项式（例如 $X^2 - 4X + 1$），找出它的根（$2 \pm \sqrt{3}$）。

如果学生的任务是求给定多项式的根，那么教师的任务则是寻找一个具有给定根的多项式。加尔松女士是一位热衷于数学教学的老师，她对求解像 $a + b\sqrt{c}$ 这样简单的二次方程感到厌倦。她希望构造更高次的方程，其解更加复杂。如同数学课中的常规问题一样，她希望保持所有系数为整数，并尽可能保持多项式的次数最低（前提是该多项式必须包含指定的根）。请通过编写程序帮助她完成教师的这一任务。

你将获得一个形如 $t = \sqrt[m]{a} + \sqrt[n]{b}$ 的数，其中 $a$ 和 $b$ 是互不相同的质数，$m$ 和 $n$ 是大于 1 的整数。

本题要求你找出 $t$ 在整数域上的最小多项式，即满足以下条件的多项式 $F(X) = a_d X^d + a_{d-1} X^{d-1} + \cdots + a_1 X + a_0$：

1. 系数 $a_0, \dots, a_d$ 均为整数，且 $a_d > 0$。
2. $F(t) = 0$。
3. 在满足上述两个条件的多项式中，次数 $d$ 最小。
4. $F(X)$ 是本原多项式，即系数 $a_0, \dots, a_d$ 的最大公约数为 1。

例如，$\sqrt{3} + \sqrt{2}$ 在整数域上的最小多项式是 $F(X) = X^4 - 10X^2 + 1$。验证 $F(t) = 0$ 如下（令 $\alpha = \sqrt{3}, \beta = \sqrt{2}$）：

$$\begin{aligned} 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 \end{aligned}$$

验证该多项式的次数确实最小则较为困难。但幸运的是，在本题给定条件下（即 $a$ 和 $b$ 为互异质数，$m, n > 1$），最小多项式的次数恒为 $m \times n$，且恒为首一多项式（即最高次项系数 $a_d = 1$）。

---

输入规范：

输入包含多个数据集，每个数据集格式如下：

a m b n

该行表示数 $\sqrt[m]{a} + \sqrt[n]{b}$。最后一个数据集后跟一行四个零（0 0 0 0）。

每行中的数字用单个空格分隔。

每个数据集满足以下条件：

1. $\sqrt[m]{a} + \sqrt[n]{b} \leq 4$
2. $m \times n \leq 20$
3. 答案的系数 $a_0, \dots, a_d$ 均在 $(-2^{31} + 1)$ 到 $(2^{31} - 1)$ 之间（含端点）。

---

输出规范：

对于每个数据集，输出其在整数域上的最小多项式 $F(X) = a_d X^d + a_{d-1} X^{d-1} + \cdots + a_1 X + a_0$ 的系数，格式如下：

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

非负整数无需添加正号（+ 或 -）。同一行中的数字用单个空格分隔，不得包含其他字符或多余空格。

---

样例输入：

3 2 2 2
3 2 2 3
2 2 3 4
31 4 2 3
3 2 2 7
0 0 0 0

样例输出：

1 0 -10 0 1
1 0 -9 -4 27 -36 -23
1 0 -8 0 18 0 -104 0 1
1 0 0 -8 -93 0 24 -2976 2883 -32 -3720 -23064 -29775
1 0 -21 0 189 0 -945 -4 2835 -252 -5103 -1260 5103 -756 -2183