Fraction Subtraction

Time limit1sMemory limit128 MB

Summary
For each fraction b/n, list every numerator a and denominator m with a >= 0, m > 0 such that the wrong subtraction (a-b)/(m-n) equals the correct one a/m - b/n.
Level

Medium7 of 10

Topics
Number theory, Math, Implementation, Sorting
Solved
No attempts yet

Problem

In elementary school, students learn how to subtract fractions. However, one student does the subtraction the wrong way: they subtract the denominators from each other and the numerators from each other.

For example, consider the following subtraction.

54−912\frac{5}{4} - \frac{9}{12}

The student subtracts denominator from denominator and numerator from numerator, computing it like this:

54−912=5−94−12=−4−8=48=12\frac{5}{4} - \frac{9}{12} = \frac{5 - 9}{4 - 12} = \frac{-4}{-8} = \frac{4}{8} = \frac{1}{2}

Surprisingly, there are cases where this incorrect method gives the same result as the correct subtraction.

Given a fraction bn\frac{b}{n}, write a program that finds every aa and mm satisfying the equation below, where a≥0a \ge 0 and m>0m > 0.

am−bn=a−bm−n\frac{a}{m} - \frac{b}{n} = \frac{a - b}{m - n}

Input

The input consists of several test cases. Each test case is a single line containing two integers bb and nn. (1≤b,n≤1061 \le b, n \le 10^6)

The last line of the input contains two zeros, and this line is not processed.

Output

For each test case, print on one line every fraction that satisfies the condition. Print the fractions in increasing order of value; if two fractions have the same value, print the one with the smaller numerator first.

Each fraction must be printed in the form a/m, with no spaces before or after the /. Print a single space between consecutive fractions on the same line.

Examples1

  1. Example 1

    Input
    9 12
    12 14
    4 12
    0 0
    
    Expected output
    0/24 5/20 8/16 8/8 5/4
    0/28 9/21 9/7
    0/24 3/18 3/6