e-olymp
Competitions

Ukrainian Olympiad in Informatics, III Stage, II Round

Козак Вус та гра

Козак Вус придумав ще одну задачу для учасників олімпіади! Дано множину з $n$ рядків $s_1, s_2, \ldots, s_n$ та число $k$. Множина рядків називається гарною, якщо: \begin{enumerate} \item Кожен рядок складається лише з $0$ та $1$; \item Довжина кожного рядка не більше $k$; \item Немає рядка, що є префіксом іншого рядка. \end{enumerate} Дана множина є гарною. Аліса та Боб грають в наступну гру. Кожен з них буде ходити по черзі. За один хід можна додати один рядок у множину за умови, що ця множина залишиться гарною. Хто не зможе зробити хід - програє. Аліса починає першою, допоможіть їм визначити, хто переможе, якщо вони двоє гратимуть оптимально. \InputFile Перший рядок містить два цілі числа $n$ ($0 \le n \le 10^5, 1 \le k \le 10^{18}$)~--- кількість рядків у множині та максимальна довжина рядка у гарній множині. Далі слідує $n$ рядків. У $i$-ому рядку міститься рядок $s_i$($1 \le |s_i| \le 10^6$). Гарантується, що $\sum_{i=1}^{n}{|s_i|} \le 10^6$. Також гарантується, що початкова множина є гарною. \OutputFile Виведіть <<\t{Alice}>>, якщо переможе Аліса, або <<\t{Bob}>>, якщо переможе Боб. \Scoring \begin{enumerate} \item ($2$ бали): $n = 0$; \item ($6$ балів): $k = 2$; \item ($8$ балів): $k = 3$; \item ($12$ балів): $k \le 10$; \item ($17$ балів): $k \le 20$; \item ($20$ балів): $k \le 10^4$; \item ($35$ балів): без додаткових обмежень \end{enumerate}
Time limit 1 second
Memory limit 256 MiB
Input example #1
2 3
01
000
Output example #1
Bob
Input example #2
3 3
000
1
01
Output example #2
Alice
Input example #3
2 1
0
1
Output example #3
Bob
Author Kostya Denisov