Background

Double experience: https://www.luogu.com.cn/problem/AT_arc087_c.

Problem Description

Cossack Moustache has come up with another problem for competitive programmers.

You are given a set of $n$ strings $s_1, s_2, \ldots, s_n$ and a number $k$.

A set of strings is called beautiful if and only if:

• Each string consists only of $0$ and $1$;
• The length of each string is at most $k$;
• No string is a prefix of another string.

The given set is beautiful.

Alice and Bob are playing the following game. They take turns to make a move. In each move, they may add a string to the set, provided that after adding it, the set is still beautiful. The player who cannot make a move loses.

Alice moves first. Help determine who will win if both players play optimally.

Input Format

The first line contains two integers $n$ ($0 \le n \le 10^5, 1 \le k \le 10^{18}$), which are the number of strings in the set and the maximum allowed length of strings in a beautiful set.

The next $n$ lines follow. The $i$-th line contains a string $s_i$ ($1 \le |s_i| \le 10^6$).

It is guaranteed that $\sum_{i=1}^{n}{|s_i|} \le 10^6$.

It is also guaranteed that the initial set is beautiful.

Output Format

If Alice wins, output Alice. If Bob wins, output Bob.

2 3
01
000

Bob

3 3
000
1
01

Alice

2 1
0
1

Bob

Hint

Scoring

• (2 points): $n = 0$.
• (6 points): $k = 2$.
• (8 points): $k = 3$.
• (12 points): $k \le 10$.
• (17 points): $k \le 20$.
• (20 points): $k \le 10^4$.
• (35 points): No additional constraints.

Translated by ChatGPT 5