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
from collections import deque

sys.setrecursionlimit(10000)
INF = float('inf')

N, L = list(map(int, input().split()))
S = set()
for _ in range(N):
    S.add(input())


# 追加できるのが 01... だけで
# L が 4 とすると
# 01: 次はない
# 010: 011 がある
# 011: 010 がある
# 0100: 011, 0101 がある
# 0101: 011, 0100
# 0110: 010, 0111
# 0111: 010, 0110
# 候補の長さと L だけによって次の候補の長さと数が決まる
def grundy(size):
    """
    :param int size: 候補の長さ
    :return:
    """
    # gs = {0}
    # g = 0
    # for sz in range(size + 1, L + 1):
    #     g ^= grundy(sz)
    #     gs.add(g)
    #
    # i = 0
    # while i in gs:
    #     i += 1
    # return i
    i = 1
    while (L - size + 1) % i == 0:
        i *= 2
    return i // 2


# S の各要素からトライ木つくる
trie = {}
for s in S:
    t = trie
    for c in s:
        if c not in t:
            t[c] = {}
        t = t[c]

# 候補文字列の長さのリスト
ok_size_list = []
children = deque()
children.append((trie, 0))
while len(children) > 0:
    node, size = children.popleft()
    # 0 か 1 か片方しか行けなかったら、行けない方は S の prefix にならない
    # 両方行けない場合はどう追加しても S のいずれかが prefix になってしまうからダメ
    if len(node) == 1:
        ok_size_list.append(size + 1)
    for c, child in node.items():
        children.append((child, size + 1))

g = 0
for size in ok_size_list:
    g ^= grundy(size)
if g != 0:
    print('Alice')
else:
    print('Bob')