High School Programming League Problems Archive

Write a program to decompose a given rational number into a sum of pairwise distinct fractions: 1/n₁ + 1/n₂ + ... + 1/n_k, where n_i are positive integers.

Input

Test cases (no more than 10 000) are given in the form

where p and q are positive integers such that 1 <= p <= q <= 1 000 (p and q are separated by a single space character). After each test case, a new line character follows.

Output

For each pair p and q, decompose p/q into the sum: 1/n₁ + 1/n₂ + ... + 1/n_k. As the result, please print only the denominators sorted from the smallest to the largest, separated by spaces. A newline character should follow the solution to each test-case.

Example 1

Input:

    2 3
    3 4
    2 5
    3 7

Output:

    2 6
    2 4
    3 15
    3 11 231

Example 2

A larger test-case: input, and corresponding output.

Scoring

By solving this problem you score 10 points.