Jednym z zadań, które uczniowie regularnie wykonują na lekcjach matematyki, jest rozwiązywanie równania wielomianowego. Polega to na znalezieniu pierwiastków (na przykład $2\pm\sqrt{3}$) danego wielomianu, takiego jak $X^2-4X+1$.

Jeśli zadaniem uczniów jest znalezienie pierwiastków danego wielomianu, zadaniem nauczyciela jest znalezienie wielomianu o zadanym pierwiastku. Pani Galsone jest pełną zapału nauczycielką matematyki, znudzoną rozwiązywaniem równań kwadratowych, których rozwiązania są tak proste jak $a+b\sqrt{c}$. Chciałaby tworzyć równania wyższego stopnia o nieco bardziej złożonych rozwiązaniach. Jak zwykle w zadaniach na lekcjach matematyki, chce zachować całkowitość wszystkich współczynników i możliwie najmniejszy stopień wielomianu, pod warunkiem że ma on wskazany pierwiastek. Pomóż jej, pisząc program wykonujący zadanie nauczyciela.

Dana jest liczba $t$ postaci:

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

gdzie $a$ i $b$ są różnymi liczbami pierwszymi, a $m$ i $n$ są liczbami całkowitymi większymi od 1.

Znajdź wielomian minimalny liczby $t$ nad liczbami całkowitymi, czyli wielomian $F(X)=a_dX^d+a_{d-1}X^{d-1}+\cdots+a_1X+a_0$ spełniający następujące warunki.

1. Współczynniki $a_0,\ldots,a_d$ są całkowite i $a_d>0$.

2. $F(t)=0$.

3. Stopień $d$ jest najmniejszy wśród wielomianów spełniających powyższe dwa warunki.

4. Wielomian $F(X)$ jest pierwotny, czyli współczynniki $a_0,\ldots,a_d$ nie mają wspólnego dzielnika większego od jedności.

Na przykład wielomianem minimalnym liczby $\sqrt{3}+\sqrt{2}$ nad liczbami całkowitymi jest $F(X)=X^4-10X^2+1$. Sprawdzenie $F(t)=0$ jest tak proste jak poniższy rachunek ($\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} $$

Sprawdzenie, że stopień $F(t)$ jest rzeczywiście minimalny, jest nieco trudniejsze. Na szczęście przy warunkach z tego zadania, czyli gdy $a$ i $b$ są różnymi liczbami pierwszymi, a $m$ i $n$ są większe od jedności, stopień wielomianu minimalnego zawsze wynosi $mn$. Co więcej, jest on zawsze moniczny, czyli współczynnik przy najwyższej potędze ($a_d$) jest równy jeden.

Wejście

Wejście składa się z wielu zestawów danych, każdy w następującym formacie.

$$a\quad m\quad b\quad n$$

Ten wiersz reprezentuje $\sqrt[m]{a}+\sqrt[n]{b}$. Po ostatnim zestawie danych następuje wiersz złożony z czterech zer. Liczby w jednym wierszu są oddzielone pojedynczą spacją.

Każdy zestaw danych spełnia następujące warunki.

1. $\sqrt[m]{a}+\sqrt[n]{b}\le 4$.

2. $mn\le 20$.

3. Współczynniki odpowiedzi $a_0,\ldots,a_d$ mieszczą się między $(-2^{31}+1)$ a $(2^{31}-1)$ włącznie.

Wyjście

Dla każdego zestawu danych wypisz współczynniki jego wielomianu minimalnego nad liczbami całkowitymi $F(X)=a_dX^d+a_{d-1}X^{d-1}+\cdots+a_1X+a_0$ w następującym formacie.

$$a_d\quad a_{d-1}\quad\cdots\quad a_1\quad a_0$$

Liczby nieujemne należy wypisywać bez znaku (+ lub -). Liczby w jednym wierszu muszą być oddzielone pojedynczą spacją; wyjście nie może zawierać żadnych innych znaków ani dodatkowych spacji.

Przykład

Wejście 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

Wyjście 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