#6377. 「是男人就过8题——Pony.ai」AStringGame

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: luyanaa

题目描述

最近 Alice 和 Bob 在玩一个和字符串有关的游戏。在游戏开始之前,他们会准备 n 个字符串 s_1, s_2 \ldots s_n 和一个模板串 t , 保证这 n 个字符串都是 t 的子串。

游戏开始后,他们会轮流地执行以下操作,由 Alice 先手。

n 个字符串中选择一个字符串 s_i

s_i 末尾增加一个字符;

得到的新字符串需要是 t 的子串;

如果上述过程无法完成,当前玩家失败,假设 Alice 和 Bob 都以最优策略行动,求出谁是游戏的胜者。

输入格式

输入包含多组测试数据。

每组数据以一个非空模板串 t 开始。

第二行包含一个整数 n ,表示他们准备的字符串数量,接下来的 n 行,每行一个字符串 s_i , 输入保证所有字符串都是 t 的子串。

输出格式

对于每组测试数据,输出胜利者的姓名 Alice 或 Bob。

样例

样例输入

aaaa
1
a
abcabd
1
a

样例输出

Alice
Bob

数据范围与提示

|t|\le 10^5, n\le 100 , 输入所有字符串的总长不超过 3 \times 10^7

特别鸣谢楼天城和吉如一提供试题,数据。