Uniform Generator

Interview

Time limit1sMemory limit128 MB

Summary

For each pair STEP and MOD, decide whether seed(x+1) = (seed(x) + STEP) mod MOD cycles through all MOD values, which holds exactly when gcd(STEP, MOD) = 1.

Level: Easy3 of 10
Topics: Number theory, Math, Implementation, Simulation
Solved: No attempts yet

Problem

Computer simulations often require random numbers. One way to generate pseudo-random numbers is with a function of the form

seed(x+1) = [ seed(x) + STEP ] % MOD
where "%" is the modulus operator.

Such a function generates pseudo-random numbers (seed) between 0 and MOD-1. A drawback of functions of this form is that they always repeat the same pattern. To minimize this effect, STEP and MOD can be chosen carefully so that every value from 0 to MOD-1 appears uniformly.

For example, if STEP=3 and MOD=5, the function generates the repeating series 0, 3, 1, 4, 2. Here, running the function MOD times produces every number from 0 to MOD-1 exactly once. Because the function always produces the same seed(x+1) whenever seed(x) occurs, a function that generates every number from 0 to MOD-1 will generate pseudo-random numbers uniformly every MOD iterations.

If STEP=15 and MOD=20, the function generates 0, 15, 10, 5 (starting from seed 0). No matter which initial seed is chosen, it can never generate all of the numbers from 0 to MOD-1, so this is a poor choice of STEP and MOD.

Determine whether the given STEP and MOD generate a uniform distribution of pseudo-random numbers.

Input

The input consists of several lines. Each line contains two integers, STEP and MOD in that order ( $1 \le STEP, MOD \le 100000$ ). Input continues until the end of file.

Output

For each line of input, print one line in the following format. Print STEP right-justified in a field of width 10 (columns 1 through 10), then MOD right-justified in a field of width 10 (columns 11 through 20), leave column 21 blank, and print the verdict left-justified starting in column 22. Print "Good Choice" when choosing this STEP and MOD generates every number from 0 to MOD-1 as MOD numbers are generated; otherwise print "Bad Choice".

Separate the results of consecutive lines with a single blank line. Do not print a trailing blank line after the last result.

Examples5

Example 1

Input

3 5
15 20
63923 99999

Expected output

         3         5 Good Choice

        15        20 Bad Choice

     63923     99999 Good Choice

Example 2
Input
```
1 1
```
Expected output
```
         1         1 Good Choice
```
Example 3
Input
```
2 4
```
Expected output
```
         2         4 Bad Choice
```

Example 4

Input

7 21
7 22

Expected output

         7        21 Bad Choice

         7        22 Good Choice

Example 5

Input

1 100000

Expected output

         1    100000 Good Choice