학생들이 수학 시간에 자주 수행하는 과제 중 하나는 다항방정식을 푸는 것이다. 즉, $X^2-4X+1$과 같은 다항식이 주어지면 그 근($2\pm\sqrt{3}$)을 찾는 것이다.
학생의 과제가 주어진 다항식의 근을 찾는 것이라면, 선생님의 과제는 주어진 근을 갖는 다항식을 찾는 것이다. 열정적인 수학 교사인 Galsone 선생님은 해가 $a+b\sqrt{c}$처럼 단순한 이차방정식을 푸는 데 지쳤다. 조금 더 복잡한 해를 갖는 고차방정식을 만들고 싶다. 수학 수업의 문제에서 흔히 그렇듯, 모든 계수를 정수로 유지하고 지정된 근을 갖는다는 조건하에 다항식의 차수를 최대한 작게 하고 싶다. 선생님 쪽의 과제를 수행하는 프로그램을 작성하여 도와주자.
다음 형태의 수 $t$가 주어진다.
$$t=\sqrt[m]{a}+\sqrt[n]{b}$$
$a$와 $b$는 서로 다른 소수이며, $m$과 $n$은 1보다 큰 정수이다.
$t$의 정수 위 최소 다항식을 구하라. 이는 다음 조건을 만족하는 다항식 $F(X)=a_dX^d+a_{d-1}X^{d-1}+\cdots+a_1X+a_0$이다.
계수 $a_0,\ldots,a_d$는 정수이고 $a_d>0$이다.
$F(t)=0$.
차수 $d$는 앞의 두 조건을 만족하는 다항식 중 최소이다.
$F(X)$는 원시 다항식이다. 즉, 계수 $a_0,\ldots,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} $$
$F(t)$의 차수가 실제로 최소임을 확인하는 것은 조금 더 어렵다. 다행히 본 문제의 조건, 즉 $a$와 $b$가 서로 다른 소수이고 $m$과 $n$이 1보다 큰 경우, 최소 다항식의 차수는 항상 $mn$이다. 또한 항상 최고차항 계수가 1인 다항식이다. 즉, 최고차항의 계수($a_d$)는 1이다.
입력
입력은 여러 데이터 세트로 이루어지며, 각각 다음 형식이다.
$$a\quad m\quad b\quad n$$
이 줄은 $\sqrt[m]{a}+\sqrt[n]{b}$를 나타낸다. 마지막 데이터 세트 뒤에는 0 네 개로 이루어진 줄 하나가 있다. 같은 줄의 수들은 공백 하나로 구분된다.
각 데이터 세트는 다음 조건을 만족한다.
$\sqrt[m]{a}+\sqrt[n]{b}\le 4$.
$mn\le 20$.
답의 계수 $a_0,\ldots,a_d$는 $(-2^{31}+1)$ 이상 $(2^{31}-1)$ 이하이다.
출력
각 데이터 세트에 대해 정수 위 최소 다항식 $F(X)=a_dX^d+a_{d-1}X^{d-1}+\cdots+a_1X+a_0$의 계수를 다음 형식으로 출력하라.
$$a_d\quad a_{d-1}\quad\cdots\quad a_1\quad a_0$$
음이 아닌 정수는 부호(+ 또는 -) 없이 출력해야 한다. 같은 줄의 수들은 공백 하나로 구분하고, 그 밖의 문자나 추가 공백이 출력에 나타나서는 안 된다.
예제
입력 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
출력 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