计蒜客

  1. 题库
  2. A String Game
  3. 问答
  • 11.12%
  • 2000ms
  • 262144K

Recently Alice and Bob are playing a game about strings. Before starting the game, they should prepare $n$ strings $s_1$, $s_2$, ..., $s_n$ and a target string $t$. It's promised that each of these $n$ strings is a substring of $t$.

When the game begins, they do the following things alternately while Alice starts first:

  • Choose a string $s_i$ from the $n$ strings;
  • Append one letter to the chosen string;
  • The new string must also be a substring of $t$.

If the above things cannot be completed, the player loses the game. Suppose Alice and Bob both use optimal strategy, find who will win the game.

Input

The input consists of multiple test cases.

Each test case begins with the non-empty target string $t$, whose length will not exceed $100000$. The second line contains an integer $n$ $(1 \leq n \leq 100)$, the number of strings they prepared. Then $n$ lines follow. The $i$-th line of the following $n$ lines is the string $s_i$. The input guarantees that each of the $n$ strings must be a non-empty substring of $t$.

The total length of all strings will not exceed $30000000$.

Output

For each test case, output the winner "Alice" or "Bob" (without quotes) in one line.

忽略每行输出的末尾多余空格

样例输入

aaaa
1
a
abcabd
1
a

样例输出

Alice
Bob

题目来源

是男人就过 8 题--Pony.AI 题

想挑战这道题吗

  • main.c