Hash tables P83317


Statement
 

pdf   zip

html

"Open Addressing" is a variant of hash tables, which (simplifiedly) consists of:

Being x any key, being MAX the size of the vector where the information is stored, being h1(x), the first position where will be tried to store x (a value between 0 and MAX-1), and being inc a value (which sometimes depends on x) between 1 and MAX-1. Then, the following position where would be tried to store x in the case that h1(x) was occupied would be h2(x) = (h1(x) + inc) mod MAX, and so forth to hMAX(x) = (hMAX-1(x) + inc) mod MAX. (Notice that with inc = 1 we obtain one of the variants of hash tables that we implemented in a laboratory practice.)

For instance, if MAX = 5, h1(x) = 1 and inc = 2, the positions of the vector would be visited (if it was needed) in the following order: 1, 3, 0, 2, 4. However, if MAX = 6, h1(x) = 1 and inc = 2, the order would be: 1, 3, 5, 1, 3, 5. As you can see, in the first case all the MAX positions are visited, but not in the second one.

Write a program that decides for each combination of MAX, h1(x) and inc given, if the combination is good (visites all the positions) or it is not.

Input

Input consists of zero or more cases. Each case consists of a line with MAX, h1(x) and inc. (We assure you that 2 ≤ MAX ≤ 50000.) A line with three zeros indicates the end of the input.

Output

For each case, print in a line "good" or "bad" as required.

Public test cases
  • Input

    5 1 2
    6 1 2
    0 0 0
    

    Output

    good
    bad
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++