Egyptian Fractions

During the Middle Kingdom of Egypt, the Egyptians developed a way to write fractions. By adding a symbol to the hieroglyph for an integer, they represented the reciprocal of that integer. This made it easy to write any fraction of the form $1/n$ (called a unit fraction)—simply add the reciprocal symbol to the hieroglyph for $n$.

There was no direct method to represent a fraction of the form $m/n$, where m > 1. Instead, such a fraction was written as the sum of unit fractions. For example, the fraction $3/4$ could be written as:

Notice that multiple sums may yield the same result; for example, can also be written as:

Your task is to take a fraction and write it as a sum of unit fractions using a "greedy" search. In this approach, you repeatedly subtract the largest possible unit fraction from the remainder until you reach zero. For example, consider the fraction . The greedy search would find the sum in three steps:

Note that at each step, we subtract the largest possible unit fraction from what remains of our original fraction.

To keep solutions manageable, there is an additional requirement: Each time you subtract a unit fraction, the resulting fraction must have a denominator strictly less than $1000000$. For example, consider the fraction . The first two unit fractions to subtract are and , leaving . At this point, the largest possible unit fraction is , leaving

However, this creates a fraction with a denominator greater than $1000000$, so this unit fraction cannot be used. Move to the next possible unit fraction, , which results in

Now the answer reduces to a fraction with a denominator less than $1000000$, so this unit fraction can be used, leaving a final result of .

In this case, only one fraction was skipped. In general, you may need to skip many fractions to find a suitable one. As you search, you may need to perform calculations on fractions with large denominators; ensure you do so efficiently, or your program may take too long to run.

Also, use a data type large enough to hold the large numbers involved. Even though denominators are restricted to $1000000$, intermediate calculations may use denominators up to 10^{12}. A 64-bit integer is required to store such values (long in Java, long long in C/C++).

Finally, the nature of the greedy algorithm means it will always find some solution with denominators less than $1000000$ since any fraction can be represented as a sum of unit fractions with its own denominator. For example:

Input

The input consists of a sequence of fractions, one per line. Each line contains two integers $M$ and $N$ with 1 < M < N < 100, representing the fraction . $M$ and $N$ have no common divisors greater than $1$. The end of the input is indicated by $00$.

Output

For each input fraction , output a single line containing numbers D_1 \le D_2 \le D_3 \le \dots such that:

This must be the first sum found by the greedy algorithm while respecting the denominator limit of $1000000$. Each number should be separated by a space, with no leading or trailing whitespace.