G - Substring Game 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MiB

配点 : 600 点

問題文

英小文字からなる文字列 S が与えられます。

Alice と Bob がこの文字列を使って以下のようなゲームを行います。

  • 空文字列 T を用意する。
  • Alice から始めて両者は交互に手番をプレイする。
  • 各手番では、プレイヤーは英小文字を一つ選び、 T の末尾に選んだ英小文字を連結させる。ただし、連結させた後の T が S の部分文字列とならないような行動を取ることはできない。

先に手番をプレイできなくなったプレイヤーの負けです。

両者が最善を尽くしたとき、どちらのプレイヤーが勝つかを求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1\le T\le 10^5
  • T は整数
  • S は英小文字からなる長さ 1 以上 2\times 10^5 以下の文字列
  • 全てのテストケースにおける S の長さの総和は 4\times 10^5 以下

入力

入力は以下の形式で標準入力から与えられる。

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

各テストケースは以下の形式で与えられる。

S

出力

各テストケースに対する答えを順に改行区切りで出力せよ。

各テストケースについて、両者が最善を尽くしたとき Alice が勝つならば Alice を、Bob が勝つならば Bob を出力せよ。

入力例 1

4
ooxo
abrakadabra
atcoderbeginnercontest
baabca

出力例 1

Bob
Alice
Alice
Bob

1 番目のテストケースについて考えます。

例えば、ゲームは以下のように進行します。

  • Alice が x を選ぶ。 T= x となる。
  • Bob が o を選ぶ。 T= xo となる。
  • Alice がどの英小文字を選んで T の末尾に連結しても T が S の部分文字列となることはないため、Alice は手番をプレイすることができない。この時点で Bob の勝ちとなる。

このテストケースは Alice がどのように手番をプレイしても Bob が勝つことができます。したがって、 Bob を出力してください。

Score : 600 points

Problem Statement

You are given a string S consisting of lowercase English letters.

Alice and Bob play the following game using this string.

  • Prepare an empty string T.
  • Starting with Alice, they take turns playing.
  • On each turn, the player chooses one lowercase English letter and concatenates the chosen letter to the end of T. Here, the player cannot take an action such that T after concatenation is not a substring of S.

The player who cannot make a move first loses.

Determine which player will win when both players play optimally.

You are given T test cases; solve each of them.

Constraints

  • 1\le T\le 10^5
  • T is an integer.
  • S is a string consisting of lowercase English letters with length between 1 and 2\times 10^5, inclusive.
  • The sum of the lengths of S over all test cases is at most 4\times 10^5.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format.

S

Output

Output the answers for the test cases in order, separated by newlines.

For each test case, output Alice if Alice wins when both players play optimally, and Bob if Bob wins.

Sample Input 1

4
ooxo
abrakadabra
atcoderbeginnercontest
baabca

Sample Output 1

Bob
Alice
Alice
Bob

Consider the first test case.

For example, the game proceeds as follows.

  • Alice chooses x. T= x.
  • Bob chooses o. T= xo.
  • No matter which lowercase English letter Alice chooses and concatenates to the end of T, T will not be a substring of S, so Alice cannot make a move. At this point, Bob wins.

In this test case, Bob can win no matter how Alice plays. Therefore, output Bob.