It is so boring in the summer holiday, isn't it? So Alice and Bob have invented a new game to play. The rules are as follows. First, they get a set of n distinct integers. And then they take turns to make the following moves. During each move, either Alice or Bob (the player whose turn is the current) can choose two distinct integers x and y from the set, such that the set doesn't contain their absolute difference |x - y|. Then this player adds integer |x - y| to the set (so, the size of the set increases by one).

If the current player has no valid move, he (or she) loses the game. The question is who will finally win the game if both players play optimally. Remember that Alice always moves first.


-----Input-----

The first line contains an integer n (2 ≤ n ≤ 100) — the initial number of elements in the set. The second line contains n distinct space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) — the elements of the set.


-----Output-----

Print a single line with the winner's name. If Alice wins print "Alice", otherwise print "Bob" (without quotes).


-----Examples-----
Input
2
2 3

Output
Alice

Input
2
5 3

Output
Alice

Input
3
5 6 7

Output
Bob



-----Note-----

Consider the first test sample. Alice moves first, and the only move she can do is to choose 2 and 3, then to add 1 to the set. Next Bob moves, there is no valid move anymore, so the winner is Alice.

Difficulty: competition

Starter code:

Solutions:
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

n = int(input())
A = list(map(int, input().split()))

GCD = A[0]
for x in A[1:]:
    GCD = gcd(GCD, x)
num = max(A) // GCD - n
if num % 2 == 0:
    print("Bob")
else:
    print("Alice")



from fractions import gcd


n = int(input())
a = list(map(int, input().split()))
mel = max(a)
for i in range(1, len(a)):
    a[0] = gcd(a[0], a[i])
print(('Bob', 'Alice')[(mel // a[0] - n) % 2])

#print('Bob' if int(input()) % 2 else 'Alice')
#argh I hate misreading the problem

import fractions
n = int(input())
a = list(map(int, input().split()))
gcd = a[0]
for x in a:
    gcd = fractions.gcd(gcd, x)
moves = max(a) // gcd - n
print('Alice' if moves % 2 else 'Bob')


import fractions, functools
n = int(input())
a = list(map(int, input().split()))
gcd = functools.reduce(fractions.gcd, a)
moves = max(a) // gcd - n
print(['Bob', 'Alice'][moves % 2])


from fractions import gcd

n=int(input())

A=list(map(int,input().split()))
A.sort()
x=A[0]
for i in range(1,n):
    x=gcd(x,A[i])

                

moves=(max(A)//x)-n

if(moves%2==0):
    print("Bob")
else:
    print("Alice")


def gcd(a, b):
  return gcd(b, a % b) if b else a

n = int(input())
A = [int(x) for x in input().split()]
A.sort()
g = 0
for x in A:
  g = gcd(x, g);
print("Alice" if (A[n-1]//g-n) % 2 else "Bob")


from fractions import gcd
n = int(input())
a = [int(x) for x in input().split()]
gg = a[0]
for i in range(1,n):
    gg = gcd(gg,a[i])
for i in range(n):
    a[i] //= gg
if (max(a) - n) % 2 == 0:
    print('Bob')
else:
    print('Alice')

def gcd(a,b):
  if b == 0:
    return a
  return gcd(b,a%b)
a = int(input())
b = list(map(int,input().split()))
c = m = 0
for x in b:
  c = gcd(c,x)
  if(x > m):
    m = x
if (m//c-a)&1:
  print("Alice")
else:
  print("Bob")



from fractions import gcd

n=int(input())

A=list(map(int,input().split()))
A.sort()
x=A[0]
for i in range(1,n):
    x=gcd(x,A[i])

                

moves=(max(A)//x)-n

if(moves%2==0):
    print("Bob")
else:
    print("Alice")

def gcd(a, b):
    c = a % b
    return gcd(b, c) if c else b

n = int(input())
t = list(map(int, input().split()))

x = gcd(t[0], t[1])
for i in t[2: ]:
    x = gcd(i, x)
print(['Bob', 'Alice'][(max(t) // x - n) % 2])

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import fractions

n = int(input())
a = list(map(int, input().split()))
m = max(a)
g = 0
for i in a:
    g = fractions.gcd(g, i)

if (m//g - n) % 2 == 0:
    print('Bob')
else:
    print('Alice')


import fractions;

n = int(input());
a = list(map(int, input().split()));
gcd = a[0];
for i in range(1, n):
	gcd = fractions.gcd(gcd, a[i]);
x = (max(a) / gcd - n)
if (x % 2 == 1):
	print("Alice");
else:
	print("Bob");

from fractions import gcd
n, f, m = int(input()), 0, 0
for x in map(int, input().split()):
    f, m = gcd(f, x), max(m, x)
print('Alice' if (m // f - n) % 2 else 'Bob')


def main():
    n = int(input())
    l = list(map(int, input().split()))
    a = l[-1]
    for b in l:
        while a:
            a, b = b % a, a
        a = b
    print(('Bob', 'Alice')[(max(l) // a - n) & 1])


def __starting_point():
    main()
__starting_point()

from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
d = gcd(a[0], a[1])
for i in range(1, n, 1):
    d = gcd(d, a[i])
m2 = max(a)
if (m2//d-n) % 2 == 1:
    print('Alice')
else:
    print('Bob')


from fractions import gcd

n = int(input())
x = list(map(int, input().split(' ')))
gcdx = x[0]
for i in x:
    gcdx = gcd(gcdx, i)
    
nums = max(x) / gcdx

if (int(nums) - n)%2 == 1:
    print("Alice")
else:
    print("Bob")


#!/usr/bin/env python3
import collections, itertools, functools, math, fractions

def solve(a):
    g = functools.reduce(fractions.gcd, a)
    r = max(a)//g - len(a)
    return 1 - r%2

def __starting_point():
    n = int(input())
    a = list(map(int, input().split()))
    print(['Alice', 'Bob'][solve(a)])



__starting_point()


from math import gcd

n = int(input())
ar = sorted(map(int,input().split()))

d =  gcd(ar[0],ar[1])

for i in range(2,n):
	d = gcd(d,ar[i])

N = max(ar)//d - n
print( "Alice" if N%2 else "Bob")


#  C:\Users\Usuario\HOME2\Programacion\ACM


# coding = utf-8
from functools import reduce
div = 1000000007
s = input()
n = int(s)
s = input()
num = list([int(x) for x in s.split(" ")])

def gcd(a,b):
	if b == 0:
		return a
	return gcd(b,a%b)

g = reduce(gcd,num)
m = max(num)

now = m/g
remain = now - len(num)
if remain%2==0:
	print("Bob")
else:
	print("Alice")


from math import gcd
from functools import reduce
n, a = int(input()), list(map(int, input().split()))
g = reduce(lambda x, y: gcd(x, y), a, 0)
print("Alice" if (max(a) // g - n) % 2 == 1 else "Bob")

import math

n = int(input())
arr = list(map(int, input().split()))

gcd = 0
for num in arr:
	gcd = math.gcd(gcd, num)

moves = max(arr) / gcd - n
if moves % 2:
	print('Alice')
else:
	print('Bob')

from fractions import gcd
from functools import reduce
n = int(input())
a = list(map(int, input().split()))
g = reduce(gcd, a)
s = max(a)//g - n
if s%2:
    print('Alice')
else:
    print('Bob')

from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
a.sort()
x=a[0]
for i in range(1,n):
    x=gcd(x,a[i])
# In the end,array will be x,2x,3x...,regardless of the initial state
moves=(max(a)//x)-n
if(moves%2==0):
    print("Bob")
else:
    print("Alice")

import fractions, functools

n = int(input())

a = list(map(int, input().split()))

gcd = functools.reduce(fractions.gcd, a)

moves = max(a) // gcd - n

print(['Bob', 'Alice'][moves % 2])



n=int(input())
l=[int(i) for i in input().split()]
def gcd(a,b):
    if b==0: return a 
    return gcd(b,a%b) 
g=0
for i in l:
    g=gcd(g,i)
no_of_moves=max(l)//g-n 
print('Alice' if no_of_moves&1 else 'Bob')