Good Password

Time limit2sMemory limit128 MB

Summary

Given a huge number K up to 10^100 and threshold L, find K's smallest prime factor and check whether it is at least L.

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

Problem

Many encryption methods use prime numbers. A common approach is to choose two very large primes and use their product as a key, relying on the fact that factoring a large number is usually difficult.

If the chosen primes are large, their product is also large. However, a large key is not always hard to factor. A large number with a small factor can still be divided easily.

You are given a key value K and an integer L. Determine whether every non-1 factor that can appear in a factorization of K is at least L.

For example, K = 143 can be divided as 11 × 13. Therefore, when L = 11, the password is good. When L >= 12, it is not good because the factor 11 is smaller than L.

Given K and L, write a program that determines whether the password is good.

Input

The first line contains two integers K and L, separated by a space.

Output

If the password is good, print GOOD. Otherwise, print BAD followed by the smallest non-1 factor of K, separated by a space.

Constraints

4 ≤ K ≤ 10^100
2 ≤ L ≤ 1,000,000

Examples2

Example 1
Input
```
143 11
```
Expected output
```
GOOD
```
Example 2
Input
```
143 12
```
Expected output
```
BAD 11
```