E - Prefix-free Game

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 700

問題文

文字列 s, t について、st の prefix でなく、ts の prefix でないとき、s, t は prefix-free であると言います。

L を正の整数とします。 文字列集合 S良い文字列集合 であるとは、次の条件が成り立つことです。

  • S の各文字列は、長さ 1 以上 L 以下であり、文字 0, 1 のみからなる。
  • S の相異なる 2 つの文字列のペアはいずれも prefix-free である。

良い文字列集合 S = \{ s_1, s_2, ..., s_N \} があります。 Alice と Bob が次のゲームで勝負します。 二人は交互に次の操作を行います。 Alice が先手です。

  • S に新しい文字列をひとつ追加する。 ただし、追加後の S は良い文字列集合のままでなければならない。

先に操作を行えなくなった方が負けです。 二人が最適に行動するとき、どちらが勝つか判定してください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq L \leq 10^{18}
  • s_1, s_2, ..., s_N はすべて相異なる。
  • \{ s_1, s_2, ..., s_N \} は良い文字列集合である。
  • |s_1| + |s_2| + ... + |s_N| \leq 10^5

入力

入力は以下の形式で標準入力から与えられる。

N L
s_1
s_2
:
s_N

出力

Alice が勝つならば Alice を、Bob が勝つならば Bob を出力せよ。


入力例 1

2 2
00
01

出力例 1

Alice

Alice が 1 を追加すると、Bob は新たに文字列を追加できなくなります。


入力例 2

2 2
00
11

出力例 2

Bob

初手で Alice が追加できる文字列は 01, 102 通りです。 初手で Alice が 01 を追加した場合は、Bob が 10 を追加すると、Alice は新たに文字列を追加できなくなります。 初手で Alice が 10 を追加した場合も、Bob が 01 を追加すると、Alice は新たに文字列を追加できなくなります。


入力例 3

3 3
0
10
110

出力例 3

Alice

Alice が 111 を追加すると、Bob は新たに文字列を追加できなくなります。


入力例 4

2 1
0
1

出力例 4

Bob

初手で Alice は新たに文字列を追加できません。


入力例 5

1 2
11

出力例 5

Alice

入力例 6

2 3
101
11

出力例 6

Bob

Score : 700 points

Problem Statement

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.


Sample Input 1

2 2
00
01

Sample Output 1

Alice

If Alice adds 1, Bob will be unable to add a new string.


Sample Input 2

2 2
00
11

Sample Output 2

Bob

There are two strings that Alice can add on the first turn: 01 and 10. In case she adds 01, if Bob add 10, she will be unable to add a new string. Also, in case she adds 10, if Bob add 01, she will be unable to add a new string.


Sample Input 3

3 3
0
10
110

Sample Output 3

Alice

If Alice adds 111, Bob will be unable to add a new string.


Sample Input 4

2 1
0
1

Sample Output 4

Bob

Alice is unable to add a new string on the first turn.


Sample Input 5

1 2
11

Sample Output 5

Alice

Sample Input 6

2 3
101
11

Sample Output 6

Bob