Problem: For strings s and t, we will say that s and t are prefix-free when neither is a prefix of the other.

Let L be a positive integer. A set of strings S is a good string set when the following conditions hold true:

* Each string in S has a length between 1 and L (inclusive) and consists of the characters `0` and `1`.
* Any two distinct strings in S are prefix-free.



We have a good string set S = \\{ s_1, s_2, ..., s_N \\}. Alice and Bob will play a game against each other. They will alternately perform the following operation, starting from Alice:

* Add a new string to S. After addition, S must still be a good string set.



The first player who becomes unable to perform the operation loses the game. Determine the winner of the game when both players play optimally.

Constraints

* 1 \leq N \leq 10^5
* 1 \leq L \leq 10^{18}
* s_1, s_2, ..., s_N are all distinct.
* { s_1, s_2, ..., s_N } is a good string set.
* |s_1| + |s_2| + ... + |s_N| \leq 10^5

Input

Input is given from Standard Input in the following format:


N L
s_1
s_2
:
s_N


Output

If Alice will win, print `Alice`; if Bob will win, print `Bob`.

Examples

Input

2 2
00
01


Output

Alice


Input

2 2
00
11


Output

Bob


Input

3 3
0
10
110


Output

Alice


Input

2 1
0
1


Output

Bob


Input

1 2
11


Output

Alice


Input

2 3
101
11


Output

Bob

Solution (in PYTHON3):

Solution:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from collections import deque

N,M = map(int,input().split())
words = [deque(input().rstrip()) for _ in range(N)]

# 深さLのfull treeの小さい方を計算してみる
def G_small():
    G = [0] * 100
    G_cum = [0] * 100
    G[0] = 1
    G_cum[0] = 1
    for n in range(1,100):
        can_make = set(G_cum[n-1]^G_cum[x] for x in range(n)) | set([G_cum[n-1]])
        rest = set(range(n+10)) - can_make
        G[n] = min(rest)
        G_cum[n] = G_cum[n-1] ^ G[n]
    return G

# print([(n,G[n]) for n in range(100)])
# G[n] = 2**ord_2(n+1)
# 値がわかれば証明は易しい

def G(n):
    n += 1
    x = 1
    while not n & 1:
        n >>= 1
        x <<= 1
    return x

def calc_grandy(words,L):
    if not words:
        return G(L)
    if len(words) == 1 and words[0] == deque():
        return 0
    words_0 = []
    words_1 = []
    for word in words:
        first = word.popleft()
        if first == '0':
            words_0.append(word)
        else:
            words_1.append(word)
    return calc_grandy(words_0,L-1) ^ calc_grandy(words_1,L-1)

g = calc_grandy(words,M)

answer = 'Alice' if g != 0 else 'Bob'
print(answer)