Una de las tareas que los estudiantes realizan habitualmente en clase de matemáticas es resolver una ecuación polinómica. Es decir, dado un polinomio, por ejemplo $X^2-4X+1$, encontrar sus raíces ($2\pm\sqrt{3}$).
Si la tarea de los estudiantes es encontrar las raíces de un polinomio dado, la tarea del profesor es encontrar un polinomio que tenga una raíz dada. La señora Galsone es una entusiasta profesora de matemáticas que está aburrida de hallar soluciones de ecuaciones cuadráticas tan sencillas como $a+b\sqrt{c}$. Quiere crear ecuaciones de mayor grado cuyas soluciones sean un poco más complicadas. Como es habitual en los problemas de clase de matemáticas, quiere mantener todos los coeficientes enteros y el grado del polinomio lo más pequeño posible, siempre que tenga la raíz especificada. Ayúdala escribiendo un programa que lleve a cabo la tarea del lado del profesor.
Se te da un número $t$ de la forma:
$$t=\sqrt[m]{a}+\sqrt[n]{b}$$
donde $a$ y $b$ son números primos distintos y $m$ y $n$ son enteros mayores que 1.
En este problema debes encontrar el polinomio mínimo de $t$ sobre los enteros, es decir, el polinomio $F(X)=a_dX^d+a_{d-1}X^{d-1}+\cdots+a_1X+a_0$ que satisface las siguientes condiciones.
Los coeficientes $a_0,\ldots,a_d$ son enteros y $a_d>0$.
$F(t)=0$.
El grado $d$ es el mínimo entre los polinomios que satisfacen las dos condiciones anteriores.
$F(X)$ es primitivo. Es decir, los coeficientes $a_0,\ldots,a_d$ no tienen divisores comunes mayores que uno.
Por ejemplo, el polinomio mínimo de $\sqrt{3}+\sqrt{2}$ sobre los enteros es $F(X)=X^4-10X^2+1$. Verificar $F(t)=0$ es tan sencillo como el cálculo siguiente ($\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} $$
Verificar que el grado de $F(t)$ es realmente mínimo es un poco más difícil. Por suerte, bajo las condiciones dadas en este problema, es decir, que $a$ y $b$ son primos distintos y $m$ y $n$ son mayores que uno, el grado del polinomio mínimo siempre es $mn$. Además, siempre es mónico: el coeficiente de su término de mayor grado ($a_d$) es uno.
Entrada
La entrada consta de varios conjuntos de datos, cada uno con el siguiente formato.
$$a\quad m\quad b\quad n$$
Esta línea representa $\sqrt[m]{a}+\sqrt[n]{b}$. Al último conjunto le sigue una línea con cuatro ceros. Los números de una línea se separan con un único espacio.
Cada conjunto de datos satisface las siguientes condiciones.
$\sqrt[m]{a}+\sqrt[n]{b}\le 4$.
$mn\le 20$.
Los coeficientes de la respuesta $a_0,\ldots,a_d$ están entre $(-2^{31}+1)$ y $(2^{31}-1)$, inclusive.
Salida
Para cada conjunto, imprime los coeficientes de su polinomio mínimo sobre los enteros $F(X)=a_dX^d+a_{d-1}X^{d-1}+\cdots+a_1X+a_0$ con el siguiente formato.
$$a_d\quad a_{d-1}\quad\cdots\quad a_1\quad a_0$$
Los enteros no negativos deben imprimirse sin signo (+ o -). Los números de una línea deben separarse con un único espacio y no pueden aparecer otros caracteres ni espacios adicionales en la salida.
Ejemplos
Entrada 1
3 2 2 2 3 2 2 3 2 2 3 4 31 4 2 3 3 2 2 7 0 0 0 0
Salida 1
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