Cossack Vus and the Game#10362
Kozak Vus has devised another challenge for the olympiad participants!
You are given a collection of strings s_1, s_2, \ldots, s_n and a number .
A set of strings is considered good if:
Each string is composed solely of the characters and ;
The length of each string does not exceed ;
No string is a prefix of any other string in the set.
The provided set is already good.
Alice and Bob are engaged in the following game. They will alternate turns. During a turn, a player can add one string to the set as long as the set remains good. The player who cannot make a move loses the game.
Alice takes the first turn. Determine who will win if both players play optimally.
The first line contains two integers (0 \le n \le 10^5, 1 \le k \le 10^{18}) — the number of strings in the set and the maximum permissible length of a string in a good set.
The next lines each contain one of the strings. The -th line contains the 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 good.
Output «Alice», if Alice will win, or «Bob», if Bob will win.
Example 1
Example 2
Example 3
( points): n = 0;
( points): k = 2;
( points): k = 3;
( points): k \le 10;
( points): k \le 20;
( points): k \le 10^4;
( points): no additional constraints