Козак Вус придумав ще одну задачу для учасників олімпіади!
Дано множину з n рядків s1,s2,…,sn та число k.
Множина рядків називається гарною, якщо:
Кожен рядок складається лише з 0 та 1;
Довжина кожного рядка не більше k;
Немає рядка, що є префіксом іншого рядка.
Дана множина є гарною.
Аліса та Боб грають в наступну гру. Кожен з них буде ходити по черзі. За один хід можна додати один рядок у множину за умови, що ця множина залишиться гарною. Хто не зможе зробити хід - програє.
Аліса починає першою, допоможіть їм визначити, хто переможе, якщо вони двоє гратимуть оптимально.
Перший рядок містить два цілі числа n (0≤n≤105,1≤k≤1018) — кількість рядків у множині та максимальна довжина рядка у гарній множині.
Далі слідує n рядків. У i-ому рядку міститься рядок si(1≤∣si∣≤106).
Гарантується, що ∑i=1n∣si∣≤106.
Також гарантується, що початкова множина є гарною.
Виведіть «Alice
», якщо переможе Аліса, або «Bob
», якщо переможе Боб.
(2 бали): n=0;
(6 балів): k=2;
(8 балів): k=3;
(12 балів): k≤10;
(17 балів): k≤20;
(20 балів): k≤104;
(35 балів): без додаткових обмежень