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:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    mod = 10**10+7
    mod2 = 10**10+9
    mod3 = 998244353
    N, L = map(int, input().split())
    dic = defaultdict(int)
    dic2 = defaultdict(int)
    dic3 = defaultdict(int)
    h_list = []
    h2_list = []
    h3_list = []
    pair = {}
    pair2 = {}
    pair3 = {}
    M = 0
    for _ in range(N):
        s = input().rstrip('\n')
        h = 0
        h2 = 0
        h3 = 0
        for i in range(len(s)):
            M += 1
            h = (h*1007 + int(s[i]) + 1) % mod
            pair[h] = (h + 1)%mod if s[i] == '0' else (h-1)%mod
            h2 = (h2 * 2009 + int(s[i]) + 1) % mod2
            pair2[h2] = (h2 + 1)%mod2 if s[i] == '0' else (h2-1)%mod2
            h3 = (h3 * 3001 + int(s[i]) + 1) % mod3
            pair3[h3] = (h3 + 1) % mod3 if s[i] == '0' else (h3 - 1) % mod3
            dic[h] = i+1
            dic2[h2] = i+1
            dic[h3] = i+1
            h_list.append(h)
            h2_list.append(h2)
            h3_list.append(h3)

    g = 0
    seen = defaultdict(int)
    seen2 = defaultdict(int)
    seen3 = defaultdict(int)
    for i in range(M):
        s, s2, s3 = h_list[i], h2_list[i], h3_list[i]
        if seen[s] and seen2[s2] and seen3[s3]:
            continue
        t = pair[s]
        t2 = pair2[s2]
        t3 = pair3[s3]
        if dic[t] == 0 or dic2[t2] == 0 or dic3[t3] == 0:
            p = [dic[s], dic2[s2], dic3[s3]]
            p.sort()
            tmp = L - p[1] + 1
            '''
            if not seen[s]:
                tmp = L - dic[s] + 1
            elif not seen[s2]:
                tmp = L - dic2[s2] + 1
            else:
                tmp = L - dic3[s3] + 1
            '''
            cnt = 0
            while tmp % 2 == 0:
                tmp //= 2
                cnt += 1
            g ^= (2**cnt)
            #print(g, s, s2, t, t2, dic[t], dic2[t2])
        seen[s] = 1
        seen2[s2] = 1
        seen3[s3] = 1

    if g:
        print('Alice')
    else:
        print('Bob')


if __name__ == '__main__':
    main()