Egyptian Fractions

The ancient Egyptians used a distinctive way to write fractions. They created a hieroglyph for each unit fraction $\frac{1}{k}$ (a fraction whose numerator is $1$) and represented other fractions by adding unit fractions together. Because this system could not directly express a fraction with a numerator greater than $1$, every fraction was written as a sum of unit fractions.

For example, $\frac{3}{4}$ can be written as

$\frac{3}{4} = \frac{1}{2} + \frac{1}{4}$

A fraction may have several such representations. For instance, $\frac{3}{4}$ can also be written as

$\frac{3}{4} = \frac{1}{4} + \frac{1}{4} + \frac{1}{4}$

Given a fraction $\frac{M}{N}$, we want to express it as a sum of unit fractions using the greedy method. The greedy method repeatedly subtracts the largest unit fraction that can be taken from the current remainder, until the remainder becomes $0$. For example, applying the greedy method to $\frac{9}{20}$ gives

$\frac{9}{20} = \frac{1}{3} + \frac{1}{9} + \frac{1}{180}$

To keep the denominators from growing too large, we add the following restriction. After subtracting a unit fraction, the denominator of the remaining fraction (in lowest terms) must always be less than $1{,}000{,}000$. If subtracting the largest possible unit fraction would leave a remainder whose denominator is $1{,}000{,}000$ or more, that unit fraction may not be used. In that case we try the next unit fractions in turn ( $\frac{1}{d+1}$ instead of $\frac{1}{d}$, increasing the denominator by $1$ each time) and use the largest one for which the remaining denominator drops below $1{,}000{,}000$.

For example, starting from $\frac{17}{69}$, the first two unit fractions are $\frac{1}{5}$ and $\frac{1}{22}$, leaving $\frac{7}{7590}$. The largest unit fraction that could be subtracted next is $\frac{1}{1085}$, but

$\frac{7}{7590} - \frac{1}{1085} = \frac{1}{1647030}$

leaves a denominator greater than $1{,}000{,}000$. So $\frac{1}{1085}$ cannot be used, and subtracting the next unit fraction $\frac{1}{1086}$ gives

$\frac{7}{7590} - \frac{1}{1086} = \frac{1}{686895}$

which satisfies the restriction. The final answer is therefore

$\frac{17}{69} = \frac{1}{5} + \frac{1}{22} + \frac{1}{1086} + \frac{1}{686895}$

Every fraction can also be written as a sum of unit fractions that all share the same denominator; for example, $\frac{M}{N}$ equals $\frac{1}{N}$ added $M$ times. Hence there is no fraction that cannot be represented by this method.

The input consists of several test cases. Each test case is a single line containing two integers $M$ and $N$ separated by a space, denoting the fraction $\frac{M}{N}$. It is guaranteed that $1 < M < N < 100$ and that $\gcd(M, N) = 1$. The last line contains 0 0, which is not processed.

For each test case, output on one line the denominators $D_1, D_2, D_3, \dots$ of the unit fractions produced by the greedy method described above, separated by spaces, so that

$\frac{M}{N} = \frac{1}{D_1} + \frac{1}{D_2} + \frac{1}{D_3} + \cdots$

holds. Print them in the order $D_1 \le D_2 \le D_3 \le \cdots$.