Time Limit: 2 second(s) | Memory Limit: 32 MB |
It's said that Aladdin had to solve seven mysteries before getting the Magical Lamp which summons a powerful Genie. Here we are concerned about the fourth mystery.
In the cave, Aladdin was moving forward after passing the pathway of magical stones. He found a door and he was about to open the door, but suddenly a Genie appeared and he addressed himself as the guardian of the door. He challenged Aladdin to play a game and promised that he would let Aladdin go through the door, if Aladdin can defeat the Genie. Aladdin defeated the Genie and continued his journey. However, let's concentrate on the game.
The game was called 'Game of Bracelets'. A bracelet is a linear chain of some pearls of various weights. The rules of the game are:
1) There are n bracelets.
2) Players alternate turns.
3) In each turn, a player has to choose a pearl from any bracelet. Then all the pearls from that bracelet, that were not lighter than the pearl, will be removed. It may create some smaller bracelets or the bracelet will be removed if no pearl is left in the bracelet.
4) The player, who cannot take a pearl in his turn, loses.
For example, two bracelets are: 5-1-7-2-4-5-3 and 2-1-5-3, here the integers denote the weights of the pearls. Suppose a player has chosen the first pearl (weight 5) from the first bracelet. Then all the pearls that are not lighter than 5, will be removed (from first bracelet). So, 5-1-7-2-4-5-3, the red ones will be removed and thus from this bracelet, three new bracelets will be formed, 1, 2-4 and 3. So, in the next turn the other player will have four bracelets: 1, 2-4, 3 and 2-1-5-3. Now if a player chooses the only pearl (weight 3) from the third bracelet, then the bracelet will be removed.
Now you are given the information of the bracelets. Assume that Aladdin plays first, and Aladdin and the Genie both play optimally. Your task is to find the winner.
Input starts with an integer T (≤ 50), denoting the number of test cases.
Each case starts with a line containing an integer n (1 ≤ n ≤ 50). Each of the next n lines contains an integer K_{i} (1 ≤ K_{i} ≤ 50) followed by K_{i} integers, denoting the weights of the pearls of the i^{th} (1 ≤ i ≤ n) bracelet. Each weight will lie in the range [1, 10^{5}].
For each case, print the case number and 'Aladdin' if Aladdin wins. Otherwise print 'Genie'. If Aladdin wins, then print an additional line, denoting the weight of pearls, one of which should be chosen in the first move by Aladdin such that he can win. Each pearl should be denoted by a pair of integers: the first integer is the bracelet number and the second integer is the weight. Sort the pearls first by the bracelet number then by the weight. And same weight in a bracelet should be reported once. Check the samples for exact formatting.
Sample Input |
Output for Sample Input |
4 2 7 5 1 7 2 4 5 3 4 2 1 5 4 2 2 5 2 2 5 2 1 5 5 2 5 2 5 3 5 5 2 5 2 5 5 7 2 7 3 2 4 5 1 5 4 |
Case 1: Aladdin (2 5) Case 2: Genie Case 3: Aladdin (1 2)(1 5) Case 4: Aladdin (2 7)(3 1)(3 5) |
Developed and Maintained by
JANE ALAM JAN |
Copyright © 2012
LightOJ, Jane Alam Jan |