A - Mex Game Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

A, B からなる長さ N+1 の文字列 S = S_0\cdots S_N が与えられます． 各 k=1, \ldots, N に対して次の問題を解いてください：

Alice と Bob が集合 X を使ってゲームをします．X ははじめ空集合で，t=1,\ldots, k の順に次の行動を行います．

  • t が奇数ならば，Alice が非負整数 x を選び，X を X\cup \{x\} に置き換える．
  • t が偶数ならば，Bob が非負整数 x を選び，X を X\cup \{x\} に置き換える．

k 回すべての行動が終わった時点での \mathrm{mex}(X) を x とするとき，文字 S_x が A ならば Alice が，S_x が B ならば Bob が勝者となります．集合 X の要素数は k 以下であるため，x = \mathrm{mex}(X) \leq k が成り立つ（したがって文字 S_x が存在する）ことに注意してください．

両者が最適に行動した場合の勝者の名前を出力してください．

\mathrm{mex}(X) とは？ 非負整数からなる有限集合 X に対し，x\notin X を満たす最小の非負整数 x を \mathrm{mex}(X) と定義します．

制約

  • 1\leq N\leq 2\times 10^5
  • S は A, B からなる長さ N+1 の文字列である．

入力

入力は以下の形式で標準入力から与えられます．

N
S

出力

N 行出力してください．i 行目には，k=i とした場合のゲームについて，両者が最適に行動した場合の勝者の名前（Alice または Bob）を出力してください．

入力例 1

2
ABB

出力例 1

Alice
Bob

k=1 とした場合のゲームの進行例の一例を次に示します．

  • Alice が x=10 を選ぶ．
  • \mathrm{mex}(X)=\mathrm{mex}(\lbrace 10\rbrace) = 0 であり，S_0 は A なので，Alice が勝利する．

k=2 とした場合のゲームの進行例の一例を次に示します．

  • Alice が x=2 を選ぶ．
  • Bob が x=0 を選ぶ．
  • \mathrm{mex}(X)=\mathrm{mex}(\lbrace 0,2\rbrace) = 1 であり，S_1 は B なので，Bob が勝利する．

入力例 2

4
AAAAA

出力例 2

Alice
Alice
Alice
Alice

入力例 3

7
BBAABABA

出力例 3

Bob
Bob
Alice
Bob
Alice
Bob
Alice

Score : 300 points

Problem Statement

You are given a string of length N+1 consisting of A and B: S = S_0\cdots S_N. For each k=1, \ldots, N, solve the following problem.

Alice and Bob will play a game using a set X, which is initially empty. For t=1,\ldots, k in this order, they will do the following action:

  • if t is odd, Alice will choose a non-negative integer x and replace X with X\cup \{x\};
  • if t is even, Bob will choose a non-negative integer x and replace X with X\cup \{x\}.

Let x be \mathrm{mex}(X) after all k actions. If the character S_x is A, Alice wins; if S_x is B, Bob wins. Note that X has at most k elements, so x = \mathrm{mex}(X) \leq k and the character S_x exists.

Print the name of the winner when both players play optimally.

What is \mathrm{mex}(X)? For a finite set X consisting of non-negative integers, \mathrm{mex}(X) is the smallest non-negative integer x such that x\notin X.

Constraints

  • 1\leq N\leq 2\times 10^5
  • S is a string of length N+1 consisting of A and B.

Input

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

N
S

Output

Print N lines. The i-th line should contain the winner's name (Alice or Bob) when both players play optimally in the game with k=i.

Sample Input 1

2
ABB

Sample Output 1

Alice
Bob

Here is a possible progression of the game with k=1.

  • Alice chooses x=10.
  • \mathrm{mex}(X)=\mathrm{mex}(\lbrace 10\rbrace) = 0, and S_0 is A, so Alice wins.

Here is a possible progression of the game with k=2.

  • Alice chooses x=2.
  • Bob chooses x=0.
  • \mathrm{mex}(X)=\mathrm{mex}(\lbrace 0,2\rbrace) = 1, and S_1 is B, so Bob wins.

Sample Input 2

4
AAAAA

Sample Output 2

Alice
Alice
Alice
Alice

Sample Input 3

7
BBAABABA

Sample Output 3

Bob
Bob
Alice
Bob
Alice
Bob
Alice