Apple Distribution Methods

Time limit1sMemory limit128 MB

Summary

Given R and G, list every common divisor N of both, printing N along with R/N and G/N as red and green apples per player.

Level: Easy3 of 10
Topics: Number theory, Math, Brute force
Solved: No attempts yet

Problem

A coach has R red apples and G green apples. The coach wants to distribute all of these apples to some of the players at a training field.

Every player who receives apples must get the same number of red apples and the same number of green apples. No apples may be left over.

Find every possible distribution method, described by the number of players who receive apples and the number of red and green apples each of them receives. Assume that there are enough players at the training field.

Input

The first line contains two integers R and G, the number of red apples and green apples.

1 <= R, G <= 1,000,000,000

Output

For each possible method, print three integers N, X, and Y on one line.

N is the number of players who receive apples.
X is the number of red apples each player receives.
Y is the number of green apples each player receives.

Each method must be printed exactly once. The methods may be printed in any order.

Examples3

Example 1
Input
```
4 8
```
Expected output
```
1 4 8
2 2 4
4 1 2
```
Example 2
Input
```
15 12
```
Expected output
```
3 5 4
1 15 12
```
Example 3
Input
```
42 105
```
Expected output
```
1 42 105
3 14 35
7 6 15
21 2 5
```