[ARC087E] Prefix-free Game

对于两个字符串 $s, t$ , 如果 $s$ 不是 $t$ 的前缀且 $t$ 不是 $s$ 的前缀，则称他们是 prefix-free 的。 给定一个正整数 $L$，如果一个字符串集合 $S$ 符合下列条件，则我们称他为 good string set： - $S$ 中的每个字符串的长度都在 $1$ 和 $L$ 之间（包括），并且之包含字符 $'0'$ 和 $'1'$ - $S$ 中的每两个的字符串都是 prefix-free 的 我们有一个 good string set $S = {s_1, s_2 ... , s_n}$，Alice 和 Bob 在玩一个游戏，他们轮流做下列操作： - 向 $S$ 中添加一个新字符串，并使 $S$ 仍是 good string set 无法进行这个操作的人输掉游戏。假设二人都按最优策略进行游戏，求谁会赢。 ## 数据范围 $1 \leq N \leq 10^5$ $1 \leq L \leq 10^{18}$ $s_1, s_2, ..., s_n$ 是不同的 ${s_1, s_2, ..., s_n}$ 是 good string set $|s_1| + |s_2| + ... + |s_n| \leq 10^5$ 翻译者：魔塔哈奇

[problemUrl]: https://atcoder.jp/contests/arc087/tasks/arc087_c 文字列 $ s $, $ t $ について、$ s $ が $ t $ の prefix でなく、$ t $ が $ s $ の 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 $ は良い文字列集合のままでなければならない。 先に操作を行えなくなった方が負けです。 二人が最適に行動するとき、どちらが勝つか判定してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ L $ $ s_1 $ $ s_2 $ $ : $ $ s_N $

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

2 2
00
01

Alice

2 2
00
11

Bob

3 3
0
10
110

Alice

2 1
0
1

Bob

1 2
11

Alice

2 3
101
11

Bob

### 制約 - $ 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 $ ### Sample Explanation 1 Alice が `1` を追加すると、Bob は新たに文字列を追加できなくなります。 ### Sample Explanation 2 初手で Alice が追加できる文字列は `01`, `10` の $ 2 $ 通りです。 初手で Alice が `01` を追加した場合は、Bob が `10` を追加すると、Alice は新たに文字列を追加できなくなります。 初手で Alice が `10` を追加した場合も、Bob が `01` を追加すると、Alice は新たに文字列を追加できなくなります。 ### Sample Explanation 3 Alice が `111` を追加すると、Bob は新たに文字列を追加できなくなります。 ### Sample Explanation 4 初手で Alice は新たに文字列を追加できません。